学步园

http://acm.hdu.edu.cn/showproblem.php?pid=3652

题意：

给你一个数N，求1-N中有多少个数满足数位中有13这个substring 和 能被13整除这两个条件的数的个数。

思路：

数位dp。这题是要求我们求满足有13子串的数的个数，那么在某一位添加什么数字的时候就会受到前面有没有13出现的影响，我们用dp[i][0] , dp[i][1] , dp[i][2] 分别表示剩下i位且前面没有出现13子串且最后一个数字不是1，前面没有出现13子串且最后一个数字是1，前面已经有13子串出现，共三种情况。但是这题题目还有一个条件就是要这个数满足能被13整除，为了达到这个目的， 我们只需要在dp的状态中增加一维来表示此前的数模13的余数是多少就行了。因此最终的状态就是：

dp[i][j][0] : 后面的i位在大小没有限制的条件下，在前面的数模13余j 且 不包括13子串且最后一个数字不是1且和前面的组合起来满足条件的数的个数；

dp[i][j][0] : 后面的i位在大小没有限制的条件下，在前面的数模13余j 且 不包括13子串且最后一个数字是1且和前面的组合起来满足条件的数的个数；

dp[i][j][0] : 后面的i位在大小没有限制的条件下，在前面的数模13余j 且 包括13子串 且和前面的组合起来满足条件的数的个数；

代码：

#include <stdio.h>
#include <string.h>
int N ;
int digit[15] , pos ;
int dp[15][15][3] ;
int Mod[10] ;

void calc(){
    pos = 0 ;
    int tmp = N ;
    while( tmp ){
        digit[ ++pos ] = tmp % 10 ;
        tmp /= 10;
    }
}


int dfs(int pos , int j, int f , int limit ){
    if( !limit && dp[pos][j][f] != -1 ) return dp[pos][j][f] ;
    if( pos == 0 ){
        if( j==0 && f==2 )  return 1 ;
        else                return 0 ;
    }

    int end = limit ? digit[pos] : 9 ;
    int sum = 0 , nj ;

    for(int i=0;i<=end;i++){
        nj = ( j + i * Mod[pos-1] % 13 ) % 13 ;
        if( f == 2 ){
            sum += dfs( pos-1 , nj , 2 , limit&(i==end) ) ;
        }
        else if( f == 1 ){
            if( i == 3 ){
                sum += dfs( pos-1 , nj ,2 ,limit&(i==end) ) ;
            }
            else if( i == 1 ){
                sum += dfs( pos-1 , nj ,1 ,limit&(i==end) ) ;
            }
            else{
                sum += dfs( pos-1 , nj ,0 ,limit&(i==end) ) ;
            }
        }
        else{
            if(i == 1){
                sum += dfs( pos-1 , nj ,1 ,limit&(i==end) ) ;
            }
            else{
                sum += dfs( pos-1 , nj ,0 ,limit&(i==end) ) ;
            }
        }
    }
    if( !limit )    dp[pos][j][f] = sum ;
    return sum ;
}

int main(){
    Mod[0] = 1 ;
    for(int i=1;i<10;i++){
        Mod[i] = Mod[i-1] * 10 % 13 ;
    }
    while( scanf("%d",&N) == 1){
        calc() ;
        memset( dp, -1, sizeof(dp) );
        int ans = dfs(pos , 0 , 0 , 1) ;
        printf("%d\n",ans) ;
    }
    return 0 ;
}