代码拍卖会

读题可知$P(1<=P<=500)$，以及拆分成9个不同长度的$11…1$串是关键。

尝试用值域划分，显然的是用DP求解。

此时我们需要的是%p意义下相同的数为一类，此时计算一个辅助数组帮忙理解有多少个%p相同的数的方案数很重要。

整理思路，发现大概率是可行的，那么辅助数组对应的就是一个循环节。

即$f_i=(f_{i-1}*10+1)\%p$，这个数是会出现循环的，则分段计算就可以得到代表有多少个1循环的数%p后为t的g[t]数组。

已知可以拆分为9个1循环数，则等价于对9个1循环数组合求出解。

然而关键是可能会出现非法或重复情况，仔细回顾，我们已经知道了%p为一类必然是此题突破口，则区分必然是在9个1循环数中。

此时的思路或许会有所混乱，假如说直接设$f[i+1][(k+s)\%p]=f[i][k]*g[s]$，则因为大小没有区分会重复。

具体定义得到说，因为g数组是无序的，所以直接选定一个为模数的数做统计不能保证合法。

因此，应该对于每一个余数内部统计，而且虽然可以从一个余数中抽出多个后缀统计答案（使用组合数以避免重复），但却不能在此之后反复统计这个余数，如何判断我们是否选过意味着，应该将选到第几个余数加到DP数组中。

保证递推则保证不会复选。将不能复选的量加入DP是一种常见方法。

所以改设为$f[i+1][j+t][(k+(t*i))\%p]+=f[i][j][k]*C(g[i]+t-1,t)$

记得取mod。本题评为乙上（原时间会更高，但如今技巧较为普及）。