套路来讲定义f[i][j][k]
表示 i位数,最高位为j,mod n为k的满足条件的数的个数
这里提供一种两维状态的方法
去掉第二维,也就是不需要最高位是几这一维
初始化时枚举 当前这一位是谁 和 之前所有位的和,转移到算上这一位的和 % n 即可
计算时枚举第i位是j的话,答案只需累加上 (i-1位的和 + j) mod n == 0的方案数即可
在mod n 意义下这样的数只有一个,可直接算出
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int N = 10;
int f[N][N * N],n;
void init()
{
memset(f,0,sizeof f);
f[0][0] = 1;
for(int i = 1;i < N;i ++)
for(int j = 0;j <= 9;j ++)
for(int k = 0;k <= n;k ++)
f[i][(j + k) % n] += f[i - 1][k];
}
int dp(int x)
{
if(!x)return 1;
vector<int> num;
while(x)num.push_back(x % 10),x /= 10;
int res = 0,last = 0;
for(int i = num.size() - 1;i >= 0;i --)
{
for(int j = 0;j < num[i];j ++)
res += f[i][(10 * n - last - j) % n];
last = (last + num[i]) % n;
if(!last)res++;
}
return res;
}
int main()
{
int l,r;
while(cin >> l >> r >> n)
{
init();
cout << dp(r) - dp(l - 1) << endl;
}
}
应该写成 if(!last&&!i)res++;
感谢,之前一直有几个数据差1,调了半天,结果看了一下,原来是我f[0][0]没赋值