传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1799
【题解】
一眼看过去，数位dp！
想了想，发现数字和最多也就是$m = 9 imes 18 = 162$种，好像不是很大。
考虑枚举每种数字和$p$，做一遍dp。
设$f_{i,j,k}$表示到第$i$位，当前真实数字模$p$余$j$，当前所有数字的和为$k$的方案数。（不考虑前导0问题）
这个可以通过一个$O(18 imes p^2 imes 10)$的动态规划解决。
接下来按数位dp套路，改成前缀和，然后分情况：
位数小于它的，枚举最高位（由于不考虑前导零），计算。
位数等于它的，先枚举最高改变的位置，再枚举改变成了什么，就能推出后面$j$和$k$的两维，统计答案了。
最后可能要再统计下端点的，可能没统计进去（视具体写法而定）
复杂度主要是算dp数组，为$O(18^2 imes m^3)$，假装能过。
按照真实的复杂度实际上只要跑4亿多次，能过（挺正常）吧
实测能过，跑的贼慢。。卡了卡常从39s跑到了9s。
可能有一些更好的记忆化写法？姿势水平不够先不管qwq
被一个数组没开大错误卡了一晚上。。。win下测一点问题没有，linux就gg了。。
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 19; const int mod = 1e9+7; ll A, B; int w[22], wn; ll f[22][210][210], bin[22]; // 到第i位，模p为j，位数和为k的方案数。 inline ll solve(ll x) { if(x<=0) return 0; ll tx = x; wn = 0; while(tx) w[++wn] = tx % 10, tx /= 10; ll ret = 0; for (int p=1; p<=wn*9; ++p) { bin[0] = 1 % p; for (int i=1; i<=wn; ++i) bin[i] = bin[i-1] * 10 % p; memset(f, 0, sizeof f); f[0][0][0] = 1; for (int i=0; i<wn; ++i) for (int j=0; j<p; ++j) for (int k=0; k<=p; ++k) for (int t=0; t<=9; ++t) if(k+t <= p) f[i+1][(j + t*bin[i]) % p][k+t] += f[i][j][k]; for (int i=wn-1; i; --i) for (int t=1; t<=9; ++t) if(p-t >= 0) ret += f[i-1][(p - t*bin[i-1]%p) % p][p-t]; for (int i=wn, las=0, las2=0; i; --i) { for (int t=(i==wn ? 1 : 0); t<w[i]; ++t) if(p-t-las2 >= 0) ret += f[i-1][(p - (las + t*bin[i-1])%p) % p][p-t-las2]; las += w[i]*bin[i-1]; las %= p; las2 += w[i]; } } int t = 0; for (int i=wn; i; --i) t += w[i]; if(x%t == 0) ++ret; return ret; } int main() { cin >> A >> B; cout << solve(B) - solve(A-1) << endl; return 0; }
卡常版本（预处理一些东西）
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 2e5 + 10; const int mod = 1e9+7; ll A, B; int w[22], wn; int bin[22], b[180][22]; ll f[22][180][180]; // 到第i位，模p为j，位数和为k的方案数。 inline ll solve(ll x) { if(x<=0) return 0; ll tx = x; wn = 0; while(tx) w[++wn] = tx % 10, tx /= 10; ll ret = 0; for (int p=1; p<=wn*9; ++p) { int *bin = b[p]; f[0][0][0] = 1; for (int i=0; i<wn; ++i) for (int j=0; j<p; ++j) for (int k=0; k<=p; ++k) for (int t=0; t<=9; ++t) f[i+1][(j + t*bin[i]) % p][k+t] += f[i][j][k]; for (int i=wn-1; i; --i) for (int t=1; t<=9; ++t) if(p-t >= 0) ret += f[i-1][(p - t*bin[i-1]%p) % p][p-t]; for (int i=wn, las=0, las2=0; i; --i) { for (int t=(i==wn ? 1 : 0); t<w[i]; ++t) if(p-t-las2 >= 0) ret += f[i-1][(p - (las + t*bin[i-1])%p) % p][p-t-las2]; las += w[i]*bin[i-1]; las %= p; las2 += w[i]; } for (int i=0; i<wn; ++i) for (int j=0; j<p; ++j) for (int k=0; k<=p; ++k) f[i][j][k] = 0; } int t = 0; for (int i=wn; i; --i) t += w[i]; if(x%t == 0) ++ret; return ret; } int main() { for (int p=1; p<=19*9; ++p) { b[p][0] = 1%p; for (int i=1; i<=19; ++i) b[p][i] = b[p][i-1]*10 % p; } cin >> A >> B; cout << solve(B) - solve(A-1) << endl; return 0; }