hdu3652-B-number（数位dp练习题4）

hdu3652--B-number（数位dp练习4）

B-number

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

Submit Status

Description

A wqb-number, or B-number for short, is a non-negative integer whose decimal form contains the sub- string "13" and can be divided by 13. For example, 130 and 2613 are wqb-numbers, but 143 and 2639 are not. Your task is to calculate how many wqb-numbers from 1 to n for a given integer n.

Input

Process till EOF. In each line, there is one positive integer n(1 <= n <= 1000000000).

Output

Print each answer in a single line.

Sample Input

Sample Output

求出1到n中含有13 且能被13整除的数的个数。

dp1[i][j][k]代表不含13的 i位的以j开头的且对13取余的数的个数

dp2[i][j][k]代表包含13的 i位的以j开头的且对13取余的数的个数

对于边界情况，要判断是不是包含了13 且能不能被13整除，当条件满足时才能被累加。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
#define LL __int64
LL dp1[12][12][13] , dp2[12][12][13] ;//dp1 i位最高位j 余数为k 不含13
int digit[12] , cnt ;
LL f(int n,int j)
{
    LL i , k = j ;
    for(i = 0 ; i < n ; i++)
        k *= 10 ;
    return k ;
}
void init()
{
    int i , j , k , l , temp ;
    memset(dp1,0,sizeof(dp1)) ;
    memset(dp2,0,sizeof(dp2)) ;
    for(j = 0 ; j < 10 ; j++)
        dp1[1][j][ j%13 ] = 1 ;
    for(i = 2 ; i <= 10 ; i++)
    {
        for(j = 0 ; j < 10 ; j++)
        {
            temp = f(i-1,j) ;
            for(k = 0 ; k < 10 ; k++)
            {
                for(l = 0 ; l < 13 ; l++)
                {
                    dp2[i][j][ (temp+l)%13 ] += dp2[i-1][k][l] ;
                    if( j == 1 && k == 3 )
                        dp2[i][j][ (temp+l)%13 ] += dp1[i-1][k][l] ;
                    else
                        dp1[i][j][ (temp+l)%13 ] += dp1[i-1][k][l] ;
                }
            }
        }
    }
    return ;
}
LL solve(LL temp)
{
    memset(digit,0,sizeof(digit)) ;
    cnt = 0 ;
    while( temp )
    {
        digit[++cnt] = temp%10 ;
        temp /= 10 ;
    }
    LL ans = 0 , i , j , flag = 0 , k ;
    for(j = 0 ; j < digit[cnt] ; j++)
        ans += dp2[cnt][j][0] ;
    temp = f(cnt-1,digit[cnt]) ;
    for(i = cnt-1 ; i > 0 ; i--)
    {
        for(j = 0 ; j < digit[i] ; j++)
        {
            for(k = 0 ; k < 13 ; k++)
            {
                if( (temp+k)%13 == 0 )
                    ans += dp2[i][j][k] ;
                if( (temp+k)%13 == 0 && ( digit[i+1] == 1&& j == 3) )
                    ans += dp1[i][j][k] ;
                else if( (temp+k)%13 == 0 && flag )
                    ans += dp1[i][j][k] ;

            }
        }
        if( digit[i+1] == 1 && digit[i] == 3 )
            flag = 1 ;
        temp = temp + f(i-1,digit[i]) ;
    }
    return ans ;
}
int main()
{
    LL n ;
    init() ;
    int i , j , k ;
    while( scanf("%I64d", &n) != EOF )
    {
        printf("%I64d\n", solve(n+1) ) ;
    }
    return 0;
}

hdu3652-B-number（数位dp练习题4）

相关推荐