这大概是我真正意义上的第一道黑题吧！
自己想出了一个大概，状态转移方程打错了一点点，最后还是得看题解。
一句话题意：求出有多少个(n)位的数，满足各个位置上的数字从左到右不下降，且被(p)整除。
刚开始没有看到数位不下降这个条件，于是自信满满的喊了一句：“这是假黑题吧！”
后来发现了，想了好久好久才找到一条规律。。。
对于任意一个(n)位的数，因为要求满足数位不下降，所以一定可以拆分成(0,1,11,111,1111,11111……)的和。
又因为数字最大是(9)，所以就是从上述数字中任选(9)个的和。
于是，我敏锐的觉察到，这是一个dp题，嘿嘿～
分析了一下，由于(n)实在太大((nleq10^{18}))所以时间复杂度肯定要去掉这个(n)。
然后，我们又会发现(p)的范围很小很小，只有(500)，于是我们很快想到模数的循环之类的。
因为这里的所有数都是由(0,1,11,111,1111,11111……)组成的，又因为这些(1)们模上(p)会出现循环。
所以我们记(cnt[i])，表示模(p)为(i)的这些11111……
显然我们需要预处理一波(cnt[])数组，直接从(1)枚举到(p)即可。
有了上面这些性质，就很好能想出如何定义状态了。
设(f[i][j][k])，表示枚举到了(cnt[i])，模(p)为(j)，选了(k)个形如1111……的数。
那么状态转移方程就很好出来了：
[f[i+1][(j+l*i)~ exttt{mod}~p][k+l]=(f[i][j][k]*T(l,cnt[i])+f[i+1][(j+l*i)~ exttt{mod}~p][k+l])
]
这里的(T(A,B)=C_{A+B-1}^{A})根据组合知识很容易求出。
那么差不多这题也完结了。
我本来以为会爆空间的，毕竟(f[501][501][11])我开的是( exttt{long~long})。结果洛谷只有(21 exttt{M})多一点点。
要注意三个问题：
- 开长整型( exttt{long long})。
- 为了防止前导(0)问题，刚开始要填满111111……
- 最好弄个滚动数组，滚掉第一维。
代码有点丑：
#include <bits/stdc++.h>
using namespace std;
typedef int _int;
#define int long long
const int mo=999911659;
int ans;
int n,p,cnt[501],beg,len,pos[501];
int A[10],c[501][11];
int f[501][501][11],a,sum;
_int main()
{
cin>>n>>p;
if (n<=p) {
for (int i=1;i<=n;++i) {
sum=sum*10+1;
sum%=p;
++cnt[sum];
}
a=sum;
}
else {
for (int i=1;i<=p+1;++i) {
sum=sum*10+1;
sum%=p;
if (cnt[sum]) {
beg=pos[sum];
len=i-pos[sum];
break;
}
++cnt[sum];
pos[sum]=i;
}
for (int i=0;i<p;++i)
if (cnt[i]&&pos[i]>=beg) {
cnt[i]=(n-beg+1)/len;
if (pos[i]-beg+1<=(n-beg+1)%len)
++cnt[i];
if ((pos[i]-beg+1)%len==(n-beg+1)%len)
a=i;
}
}
A[1]=1;
for (int i=2;i<=8;++i)
A[i]=(mo-mo/i)*A[mo%i]%mo;
for (int i=0;i<p;++i) {
c[i][0]=1;
if (cnt[i])
for (int j=1;j<=8;++j) {
c[i][j]=(cnt[i]*c[i][j-1]%mo)*A[j]%mo;
++cnt[i];
cnt[i]%=mo;
}
}
f[0][a][0]=1;
for (int i=0;i<p;++i) {
for (int j=0;j<p;++j) {
for (int k=0;k<9;++k) {
for (int l=0;l<=k;++l) {
f[i+1][j][k]+=f[i][(j-(l*i%p)+p)%p][k-l]*c[i][l]%mo;
f[i+1][j][k]%=mo;
}
}
}
}
for (int i=0;i<=8;++i)
ans+=f[p][0][i],ans%=mo;
cout<<ans;
return 0;
}