P2481 [SDOI2010] 代码拍卖会
题目大意详细题目传送门
求有多少个 \(n\) 位数 \(v=\overline{a_1a_2\cdots a_n}\) 满足每一位都小于等于右边的下一位，且有给出 \(p\) 使 \(v|p\)。
\(n\leq10^{18},p\leq500\)
思路
注意到 \(n\) 很大，但 \(p\) 很小，所以基本的数位 dp 就无法做到了。这时候注意到一个神仙的转换，每一个 \(v\) 都可以转换成不同位的全 \(1\) 构成。如 \(111222333=111111111+111111+111\)。似乎我们可以将原问题转化成考虑不同长度的动规。
发现 \(p\) 很小，所以我们把这些 \(1\) 都在模 \(p\) 意义下考虑即可。设 \(g_i\) 表示的是所有 \(\) 长度的串有几个 \(\bmod p=i\)。一会儿讲具体求法。
于是就有 \(f_{i,j}\) 表示的是当前考虑到了所有 \(\bmod p=i\) 的数，构成余数为 \(j\) 的方案数。但是发现会有重复，因为在更新时会有进位产生。
所以有状态 \(f_{i,j,k}\) 表示考虑到考虑到了所有 \(\bmod p=i\) 的数，构成余数为 \(j\) 的方案数，一共使用了 \(k\) 个 \(1\) 的后缀。所以这样的话每一次考虑就最多有 \(9\) 个叠加，所以无法产生进位不会重复计算。得到转移公式：
\
这个转移式的意思就是 \(g_i\) 中选 \(o\) 个同类后缀的数量再乘原来的。
答案就是 \(\sum f_{p,0,i}\)。但是注意到不能有前导零，所有至少有一个 \(n\) 位 \(1\) 来进行占位，所以 \(k,o\) 都不能枚举到 \(9\)，只能从 \(0\) 到 \(8\)。
考虑 \(g\) 的求法。对于一个长度为 \(i\) 的后缀 \(f_i\) 在模 \(p\) 的情况下可以有转移 \(f_i=(f_{i-1}*10+1)\bmod p\)，则发现如果出现一个之前已经出现过的 \(f_i\) 就说明出现了循环节（因为模的性质），且这个循环节会很短，所以每一个 \(g\) 我们只要看最初出现的位置同样在整个到 \(n\) 中有几个循环节包括了即可。
然后特别的我们要同时处理一下 \(f_n\) 的值，因为在初始化时我们预先设定了一个长度为 \(n\)。
代码
#include#define int long longusing namespace std;typedef long long ll;const ll MAXP=500+5;const ll MOD=999911659ll;ll inv;ll Cx(ll n,ll m){ ll ans=1; for(ll i=n-m+1;in>>p; inv=1; for(int i=2;i
页:
[1]