自动搬运

查看原文

来自洛谷，原作者为

	Imakf **

搬运于2025-08-24 21:38:11，当前版本为作者最后更新于2020-01-13 22:06:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题意转化

本题的转化非常妙妙！

对于任何一个猪猪举牌的方案，都可以看做 $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$ 分成三段：

• 未进入循环段

• 循环段

• 不完整循环段

暴力统计 未进入和不完整 的，用循环节搞定循环的就好了。

代码如下：

#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;
}

​```