UVA上的题目质量真的很高，而且今天这个题目做得我感觉有点招架不住啊。题目描述：
Description
I | Next generation contest – 4 | Time Limit – 4secs | Investigating Div-Sum Property |
|
An integer is divisible by 3 if the sum of its digits is also divisible by 3. For example, 3702 is divisible by 3 and 12(3+7+0+2) is also divisible by 3. This property also holds for the integer 9.
In this problem, we will investigate this property for other integers.
Input
The first line of input is an integer T(T<100) that indicates the number of test cases. Each case is a line containing 3 positive integers A, B and K. 1 <= A <= B < 2^31 and 0<K<10000.
Output
For each case, output the number of integers in the range [A, B] which is divisible by K and the sum of its digits is also divisible by K.
Sample Input | Output for Sample Input |
3 1 20 1 1 20 2 1 1000 4 | 20 5 64 |
ProblemSetter: Sohel Hafiz
Special Thanks: Ivan Krasilnikov
明显的一个数位dp呢。
一开始我的想法是对于a，b先求出b总共有多少位，再把a和b分解依次求出来。
结果无论如何优化常数，依然是TLE。
在网上看到神牛们写的博客，才发现dp也是有很大的优化余地的。
比如，这个题目，我首先不管a，b具体数字是多少，而是盲目地把所有多少位的值全部算了出来，显然这是一种十分费时间的过程（不过顺便说一句，UVA上真的卡时间卡的很紧）。
正解应该是对于给定的数，从高位到低位进行dp。对于处在某一位的数a[i]，可取值为0-(a[i]-1 )。
这样就可以迅速的求出答案了。
上代码！（参考自无名神犇）。
＃i nclude <iostream>
＃i nclude <cstdio>
＃i nclude <cstring>
using namespace std;
int f[12][115][115],A,B,k,n,m;
int a[12];
int count(int x)
{
memset(f,0,sizeof f);
for (int i=10; i>=0; i--) a[i]=x%10,x/=10;
int s1=0,s2=0;
for (int t=0; t<10; t++)
{
s1=(s1+a[t])%k;
s2=(s2*10+a[t])%k;
for (int i=0; i<k; i++)
for (int j=0; j<k; j++)
for (int h=0; h<10; h++)
{
f[t+1][(i+h)%k][(10*j+h)%k]+=f[t][i][j];
}
for (int i=0; i<a[t+1]; i++)
f[t+1][(s1+i)%k][(s2*10+i)%k]++;
}
int ans=f[10][0][0];
if ((s1+a[10])%k==0 && (s2*10+a[10])%k==0) ans++;
return ans;
}
int main()
{
int T;
scanf("%d",&T);
while (T--)
{
scanf("%d%d%d",&A,&B,&k);
if (k>111)
{
printf("0\n");
continue;
}
m=count(B)-count(A-1);
printf("%d\n",m);
}
return 0;
}
