P2481 SDOI2010代码拍卖会
$ solution: $
这道题调了好久好久，久到都要放弃了。洛谷的第五个点是真的强，简简单单一个1，调了快4个小时！
这道题第一眼怎么都是数位DP，奈何数据范围太大，只能找性质。而这道题最重要的一个性质也很套路（敲难想），因为我们所有的方案都是 $ 111112223333 $ 这样的数，我们要求的是它的大小模 $ p $ ，所以我们考虑将它用加法拆解。于是我们惊奇的发现它可以转化成（以上面那个数为例） $ 111111111111+1111111+1111=111112223333 $ 。正因为数位上的数字单调不降，所以它可以表示为不超过9个形似 $ 111...111 $ 的数的和！
而这种形似 $ 1111...1111 $ 的数，我们可以发现，如果我们依次枚举它的长度（ $ 1,11,111,1111...... $ ）这些数在模 $ p $ 意义下一定会产生循环节。于是我们将在模 $ p $ 意义下同余的这类数归到一起，然后用一个数组 $ g[i] $ 记录模 $ p $ 意义下为 $ i $ 的形如 $ 11111...111 $ 的数的个数。（因为 $ p $ 不大，所以不用枚举多久就能找到循环节）
于是题目的意思就被转换成：从所有的 $ g[i] $ 中找出（不超过）九个数，使得它们的下标之和能被 $ p $ 整除！（为什么是下标之和？因为上面说了 $ g[i] $ 中所有的形如 $ 1111...111 $ 的数在模 $ p $ 意义下为 $ i $ ！）
所以这道题就变成了一道计数类DP，我们设 $ f[i][j][o] $ 表示：已经选完了下标为 $ [0,i-1] $ 的数，从中选了 $ o $ 个形如 $ 1111...11 $ 的数，它们的和模 $ p $ 等于 $ j $ 的方案数。 考虑它的转移，如果我们要从下标为 $ i $ 的数里选出 $ k $ 个数，显然这 $ k $ 个数是可以重复的，他们的贡献都为 $ i $ ，所以相当我们从 $ g[i] $ 个数里可重复的选出 $ k $ 个数（不论怎么选他们的和都为 $ k*i $ ），根据组合计数原理这样的方案有 $ C_{g[i]+k-1}^{~~~~~k} $ 种。为了方便博主代码里会用 $ C[i][k] $ 代替 $ C[~g[i]+k-1~][k] $ 。
$ f[i+1][~(j+ki)~mod~p~][o+k]=f[i][j][o]C[i][k] $
$ code: $
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define db double
#define rg register int
using namespace std;
const int mod=999911659; //答案的模数
ll n;
ll g[505]; //记录余数为i的形如11111的数的个数
int p,vn,ans; //循环节长度，小模数
int a[505]; //记录余数上一次的位置（找循环节用）
int inv[11]; //逆元
int c[505][11]; //组合数
int f[505][505][11]; //计数类DP
inline int qr(){
register char ch; register bool sign=0; rg res=0;
while(!isdigit(ch=getchar()))if(ch=='-')sign=1;
while(isdigit(ch))res=res*10+(ch^48),ch=getchar();
if(sign)return -res; else return res;
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
scanf("%lld%d",&n,&p); inv[1]=1;
if(n<=p) for(rg i=1;i<=n;++i) vn=(vn*10+1)%p,++g[vn];
else{ rg tot=1%p,m,l;
for(rg i=1;i<=p+1;++i){
if(a[tot]){ l=a[tot]; m=i-l; break;} //找到循环节，计算循环节长度
a[tot]=i; ++g[tot]; tot=(tot*10+1)%p; //记录当前余数出现位置，继续寻找
}
for(rg i=0;i<p;++i)
if(a[i]&&a[i]>=l){
g[i]+=(n-a[i])/m%mod; //记录所有余数为i的形如11111的数的个数
if((a[i]-l+1)%m==(n-l+1)%m) vn=i; //记录长度为 n 的形如1111的数的余数，后面初始DP时有用
}
}
for(rg i=2;i<9;++i) inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod; //线性递推求逆元
for(rg i=0;i<p;++i){ c[i][0]=1; if(!g[i])continue;
for(rg j=1;j<9;++j,g[i]=(g[i]+1)%mod) //注意最后还有个++g[i]！！！
c[i][j]=(ll)c[i][j-1]*g[i]%mod*inv[j]%mod; //用性质求i较大,j较小的逆元
}
f[0][vn][0]=1; //最开始有一个长度为n的形如1111111111的数
for(rg i=0;i<p;++i)
for(rg j=0;j<p;++j)
for(rg o=0;o<9;++o)
for(rg k=0;k<9-o;++k) //枚举取出多少个余数为i的形如的11111111的数
(f[i+1][(j+k*i)%p][k+o]+=(ll)f[i][j][o]*c[i][k]%mod)%=mod;
for(rg i=0;i<9;++i) ans=(ans+f[p][0][i])%mod; //计算答案
printf("%d
",ans);
return 0;
}