这是一道正式比赛的题目 数据范围是 10^999 ~ 10^1000 的两个整数以及一个k我记得好像是不超过100，计算两个数中间有多少个每一位相乘最后和k取摸等于0的数。这道题对于不会按位dp的人是一道很难的题。但是如果会按位dp的话那是一道很容易的题。
先看看这个问题 在int能够存下的两个数中间有多少个每一位相加最后和k取摸等于0的数。首先枚举每一位从低位向高位枚举，每一位有10种取值 0,1,2,3,4,5,6,7,8,9，dp[i][j][p] 代表枚举到第i为最后摸k等于j的个数p代表是否可能会超过这一位，一层层的枚举就可以求得最终答案。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stdio.h>
#include <string.h>
using namespace std; typedef int LL;
char a[22];
char b[22];
int dp[22][99][4];
int main()
{
int i,j,d,p,s;
int n;
LL A,B;
int ans;
while(scanf("%d %d %d",&A,&B,&n)==3)
{
sprintf(b,"%021d",A);
sprintf(a,"%021d",B);
memset(dp,0,sizeof(dp));
for (i=0;a[i];++i)
a[i]-='0',b[i]-='0';
dp[0][0][3]=1;
ans=0;
for (i=0;i<20;i++)
{
for (j=0;j<n;j++)
for (p=0;p<=3;p++)
for (s=0;s<=9;s++)
{
if ((p&1)&&s>a[i+1])
continue;
if ((p&2)&&s<b[i+1])
continue;
int buff=0;
if (s==a[i+1]&&(p&1))
buff+=1;
if (s==b[i+1]&&(p&2))
buff+=2;
dp[i+1][(j+s)%n][buff]+=dp[i][j][p];
}
}
i=20;
j=0;
for (p=0;p<=3;p++)
ans+=dp[i][j][p];
printf("%d\n",ans);
}
return 0;
}
如果这个问题会了的话那之前的问题就很容易解决了，从时间复杂度上看1000位的数字都是浮云，前面的999只是想让那些想打表找规律的人望而却步而已。