题解 P2481 【[SDOI2010]代码拍卖会】

## 题意转化 本题的转化非常妙妙！ 对于任何一个猪猪举牌的方案，都可以看做 $9$ 个以内的**若干 “$1$ 的后缀”相加而成**！ 感性理解如下图：  于是我们把一个方案拆成了若干的形如 $00000...11111$ 的数字相加！ ----- 题目中让我们求 $\mod p$ 意义下为 $0$ 的方案数。 想想怎么做？ 我们可以把一个数分割成若干个 $000000...11111$ 的和。 所以我们可以计算出 $n$ 个 “$1$ 的后缀”在 $\mod p$ 意义下 的值。 因为可以选至多 $9$ 种后缀，所以就可以跑 $O(n^9)$ 暴力！ ~~然而这一个点都过不去啊~~ 其实我们可以直接把 $\mod p$ 意义下有相同数值的后缀看成同一类 比如 $11$ 和 $1$ 在 $\mod 5$ 意义下是同一类。 **不妨记 $g[i]$ 为 $\mod p$ 意义下[余数是 $i$ 的“$1$ 的后缀”]的数量。** (最后再讲 $g[i]$ 的求法，想看可以直接跳) 我们就可以不用暴力 而是做一个背包的转移就好了！ ## 背包 设 $dp[i][j][s]$ 表示当前考虑到余数为 $i$ 的 “$1$ 的后缀”，此前已经放上了 $j$ 个“$1$ 的后缀”，此时构成的数字的 $\mod p$ 的余数是 $s$ 的方案数。 枚举“$1$ 的后缀”$\mod p$ 意义下的余数 $O(p)$，记为 $i$。 枚举当前已经铺了几个“$1$ 的后缀”。$O(9)$，记为 $j$。 为什么是 $O(9)$，因为最左边的猪是不能出价为 $0$ 的，**所以最初要强制铺一层全 **$1$。 枚举当前这种 “$1$ 的后缀”铺了几个。$O(9)$，记为 $s$。 枚举转移过来的状态$\mod p$ 意义下的余数。$O(p)$，记为 $d$。 则转移方程是： $$dp[p][s+j][(d+s*i+p)\%p]+=\sum\limits \dbinom{g[i]+s-1}{s}dp[p-1][j][d]$$ 这个 $\dbinom{g[i]+s-1}{s}$ 是什么呢？ 就是在 $g[i]$ 中选 $s$ 个同种 “$1$ 的后缀”有多少种不同的方法！ 证明即隔板法。 复杂度即 $O(81p^2)$ 至于怎么计算这个组合数，直接按定义计算就好。 ---- ## 循环节的计算 那么怎么计算 $g[]$ 数组呢？ ~~普及组知识？~~ 定义 $s_i$ 表示 $i$ 个 $1$ 连起来形成的数, $f_i$ 为它在 $\mod p$ 意义下的值。 如 $s_5=11111$ $f_3=1\mod 5$ 则显然有 $f_i=(10\times f_{i-1}+1)\%p$ 显然这柿子在 $2p$ 次迭代内必然会出现循环。 可以把 $f_i$ 分成三段： - 未进入循环段 - 循环段 - 不完整循环段 暴力统计 未进入和不完整 的，用循环节搞定循环的就好了。 代码如下： ```cpp #include <cstring> #include <iostream> using namespace std; #define mod (999911659LL) #define MX (500 + 5) #define LL long long LL qpow(LL x ,LL y ,LL P){ if(!y) return 1; if(y == 1) return x; LL t = qpow(x ,y >> 1 ,P); if(y & 1) return t * t % P * x % P; return t * t % P; } LL g[MX] ,n ,p ,cycLen ,cycstNum; int cycle[MX * MX] ,first[MX]; LL dp[MX][11][MX]; LL C(LL n ,LL m){ if(m < 0) return 0; LL fz = 1 ,fm = 1; for(int i = 0 ; i < m; ++i){ (fz *= n - i) %= mod; (fm *= m - i) %= mod; } return fz * qpow(fm ,mod - 2 ,mod) % mod; } int main(){ // cout << C(10 ,7); memset(first ,-1 ,sizeof first); cin >> n >> p; cycle[0] = 1 % p; first[1 % p] = 0; LL addition = 0; // first 是该数第一次出现的位置 // cycle 是按顺序出现的数 %p for(int i = 1 ; ; ++i){ cycle[i] = (cycle[i - 1] * 10 + 1) % p; if(~first[cycle[i]]){ for(int j = 0 ; j < i && j < n; ++j) g[cycle[j]]++ ,addition = cycle[j]; n -= i; cycstNum = cycle[i]; cycLen = i - first[cycle[i]]; break; } first[cycle[i]] = i; } n = max(n ,0LL); LL times = n / cycLen; for(int i = 0 ; i < cycLen ; ++i) g[cycle[i + first[cycstNum]]] += times; LL nn = n % cycLen; for(int i = 0 ; i < nn ; ++i) g[cycle[i + first[cycstNum]]]++ ,addition = cycle[i + first[cycstNum]]; for(int i = 0 ; i < p ; ++i) g[i] %= mod; // 因为我很懒，按照上文博客 // 在计算 dp[0][][] 的时候会调用 dp[-1][][] 导致 RE // 所以我是倒着来的，把 dp[0] 变成 dp[p] ，dp[1] 变成 dp[p - 1]... dp[p + 1][0][addition] = 1; // 此处 addition 是强制要求选择一次全 111111... 造成的代价 for(int i = 0 ; i < p ; ++i){ // 枚举使用的 0000...1111 %p 意义的值 for(int j = 0 ; j < 9 ; ++j){ // 枚举已经使用次数 for(int s = 0 ; s + j < 9 ; ++s){ // 枚举当前使用次数 LL multi = C(g[i] + s - 1 ,s); for(int d = 0 ; d < p ; ++d){ // 枚举已经的余数 // if(dp[p - i + 1][j][d]){printf("dp[%lld][%d][%lld] += multi(%lld) * dp[%lld][%d][%d](%lld);\n" ,p - i ,s + j ,(d + s * i) % p ,multi ,p - i + 1 ,j ,d ,dp[p - i + 1][j][d]);} (dp[p - i][s + j][(d + s * i) % p] += multi * dp[p - i + 1][j][d]) %= mod; } } } } LL Ans = 0; for(int i = 0 ; i < 9 ; ++i){ (Ans += dp[1][i][0]) %= mod; } cout << Ans << endl; return 0; } ​``` ```