要求找出范围内含有“13”且能被13整除的数字的个数

可以使用数位dp

dp[i][j][0] 表示长度为i，余数为j，不含13的数字的个数

dp[i][j][1] 表示长度为i，余数为j，3开头的数字的个数

dp[i][j][2] 表示长度为i，余数为j，含有"13"的数字的个数

index[1] = 1;

for(i=2; i<11; ++i)

　　index[i] = (index[i-1] * 10) % 13;

index[i] 存储的为1,10,100,1000,10000 % 13 的余数

那么，状态转移方程详见源代码

1 #include 
      
        2 int dp[11][13][3]; 3 int index[11]; 4 int num[11]; 5 void init() 6 { 7     int i,j,k; 8     index[1] = 1; 9     for(i=2; i<11; ++i)10         index[i] = (index[i-1]*10) % 13;11     dp[0][0][0] = 1;12     for(i=1; i<11; ++i)13     {14         for(k=0; k<13; ++k)15         {16             //（1）17             dp[i][(index[i]+k)%13][0] -= dp[i-1][k][1];18             //长度为i-1,余数为k的不含13的数字前面加上3,-->长度为i-1，余数为k的3开头的个数19             dp[i][(index[i]*3+k)%13][1] += dp[i-1][k][0];20             //长度为i-1，余数为k的3开头的数字前面加上1-->长度为i，余数为(index[i]+k)%13含13的数字个数21             dp[i][(index[i]+k)%13][2] += dp[i-1][k][1];22             for(j=0; j<10; ++j)23             {24                 //长度为i-1，余数为k的不含13的数字前面加上j-->长度为i，余数为(index[i]*j+k)%13不含13的数字个数25                 //但是dp[i-1][k][0] 里面是包含dp[i-1][k][1]的，当加上数字1时，成为了含有13的数字，这里多加，所以在（1）处减去26                 dp[i][(index[i]*j+k)%13][0] += dp[i-1][k][0];27                 //长度为i-1，余数为k的含13的数字前面加上j-->长度为i，余数为(index[i]*j+k)%13含13的数字个数28                 dp[i][(index[i]*j+k)%13][2] += dp[i-1][k][2];29             }30         }31     }32 }33 int getAns(int n)34 {35     int i,j,k,len=0,ans=0;36     while(n)37     {38         num[++len] = n % 10;39         n /= 10;40     }41     num[len+1] = 0;42     bool flag = false;43     int t = 0,mod;44     for(i=len; i>=1; --i)45     {46         for(k=0; k<13; ++k)47         {48             if(num[i]>1 && !flag)//第i位取149             {50                 mod = (index[i]+k+t)%13;//第i位取1时余数为mod51                 if(mod==0) ans += dp[i-1][k][1];//如果余数为0，那么就加上3开头的数字个数52             }53             if(num[i+1]==1 && num[i]>3 &&!flag)//第i+1位为1，第i位取3.54             {55                 mod = (t + k) % 13;//第i+1位为1，第i位取3的余数为mod56                 if(mod==0) ans += dp[i][k][1];//如果余数为0，那么就加上3开头的数字个数57             }58             for(j=0; j
      

数位dp的难点就在于状态的转移，还有统计。

关键要弄懂它统计的原理。

http://www.cnblogs.com/justPassBy/p/4275226.html