「SOL」Nondivisible Prefix Sums(AtCoder)

AGC 还是一如既往地难（尤其是第一题( ╯□╰ )）

---

# 题面

给定正整数 $n$ 以及质数 $p$，求有多少个数列 $a_1,a_2,\cdots,a_n$，满足

• $1\le a_i\le p$；
• 存在一种将 $\{a_i\}$ 重新排列为 $\{b_i\}$ 的方案，使得 $\forall i\in[1,n],\sum\limits_{j=1}^ib_j\bmod p\neq 0$，换句话说，不存在 $b$ 的前缀和是 $p$ 的倍数。

数据规模：$1\le n\le5000$，$2\le p\le10^8$。

---

# 解析

如果 $\sum a_i\bmod p=0$，一定不满足条件，先把这个情况给排除。也就是说下面的解析都在 $\sum a_i\not\equiv0$ 的前提条件下。

结论

记 $a_i$ 中元素 $k$ 出现的次数为 $c_k$，并且其中出现次数最多的一个元素（多个则任选一个）为 $r$，则数列 $a_i$ 是合法的当且仅当

$$c_r\le\sum_{i=1}^n[a_i\neq r] (p-a_i)+p-1=\sum_{i\neq r}(p-i)c_i+p-1$$

我们再对上述结论做一个小处理，因为 $r$ 是存在逆元的，可以给每个 $a_i$ 都乘上 $r^{-1}$，显然若 $\{a_i\}$ 是合法的，则 $\{a_ir^{-1}\}$ 也是合法的。那么就强制要求了出现次数最大的数是 $1$。

考虑证明这个结论。

证明

需要判断是否存在满足条件的 $\{a_i\}$ 的重排 $\{b_i\}$，不妨从后往前决策 $b_i$ 是哪一个数。 可以理解成这样一个过程：从数轴上的 $\sum a_i$ 位置出发，每一步可以向负方向走 $b_i$ 的距离，不可以经过 $p$ 的倍数的点。 反证，若 $c_1\gt\sum_{i>1}(p-i)c_i+p-1$，即 $c_1\ge p+\sum_{i>1}(p-i)c_i$，移项可得 $$ \sum_{i=1}ic_i\ge p+\sum_{i>1}pc_i \Rightarrow \small\sum a_i\ge p\Big(1+\sum_{i>1} c_i\Big) $$ 要从数轴上 $\sum a_i$ 回到原点，中间会**跨过** $\lfloor\frac{\sum a_i}{p}\rfloor$ 个 $p$ 的倍数点，根据上面的分析，这样的倍数点有大于等于 $(1+\sum_{i>1}c_i)$ 个，而要跨过这些点，必须要走距离大于 $1$ 的一步，可以理解成「消耗」一个大于 $1$ 的 $a_i$。 这就要求大于 $1$ 的 $a_i$ 的数量大于等于需要跨过的点的数量，而 $\sum_{i+1}a_i$ 是严格小于跨过的点数的，所以这样的 $\{a_i\}$ 一定不满足条件。必要性成立。 若 $\{a_i\}$ 满足条件，构造一种方案以证明其充分性。初始的序列 $\{b_i\}$ 为空，考虑每次在末尾加入当前剩余数量最多的元素 $x$： - 若加入后前缀和不是 $p$ 的倍数，则合法； - 否则加入另一个数 $y$。 如果这样构造不合法，即只剩下 $x$ 但是 $x$ 不能加入当前数列。并且剩下的 $x$ 至少有两个，否则 $p\mid\sum a_i$。 这意味着 $x$ **一直是**剩余数量最多的元素。若存在某个时刻 $y$ 的剩余数量超过 $x$，则在之后的构造中，$y$ 与 $x$ 的剩余数量之差始终不超过 $1$，不可能最后剩下两个及以上的元素。 换句话说，在我们最初的假设中，$x$ 就是 $1$。 那么我们可以观察一下这样构造出来的数列长什么样，大概是： $$ \overbrace{1,1,\dots,1}^{p-1},a_{t_1},\overbrace{1,1,\dots,1}^{p-a_{t_1}},a_{t_2},\overbrace{1,1,\dots,1}^{p-a_{t_2}},a_{t_3},\dots $$ 什么时候会不合法呢？就是当所有大于 $1$ 的 $a_i$ 都放完后还剩余了 $1$，那么此时 $1$ 的数量应严格大于 $(p-1)+\sum_{a_i>1}(p-a_i)$，与结论的条件不符。故这样构造一定合法，充分性得证。

考虑简单容斥，从所有满足 $p\nmid\sum a_i$ 的 $\{a_i\}$ 中减去不符合上述结论的。

考虑决策所有大于 $1$ 的 $a_i$ 构成的数列，然后把 $1$ 插入到数列中。可以 DP，记 $f(cnt,sum)$ 表示当前由大于 $1$ 的 $a_i$ 构成的数列长度为 $cnt$，$\mathbf{p-a_i}$ 之和为 $sum$ 的方案数。

$$f(i,j)=\sum_{k=1}^{\min\{p-1,j\}}f(i-1,j-k)$$

那么不符合结论的 $\{a_i\}$ 则为

$$\sum_{cnt}\sum_{sum}[n-cnt\not\equiv sum][n-cnt\ge p+sum]f(cnt,sum)\binom{n}{cnt}(p-1)$$

组合数 $\binom{n}{cnt}$ 即插入 $1$ 的方案数，再乘上 $(p-1)$ 是因为我们默认了出现次数最多的是 $1$，实际上 $1\sim p-1$ 都可以。

注意 DP 的两维状态的取值范围，显然 $cnt$ 只需要 $[0,n]$。而 $sum$ 的取值范围需要分析：注意到 $f(cnt,sum)$ 对答案有贡献需要满足 $n-cnt\ge p+sum$，那么 $sum$ 也不能超过 $n$。

所以只需进行一个状态数是 $\mathcal{O}(n^2)$ 的 DP，经过前缀和优化可以 $\mathcal{O}(1)$ 转移。

总复杂度 $\mathcal{O}(n^2)$。

---

# 源代码

/*Lucky_Glass*/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 5005, MOD = 998244353;
#define con(type) const type &
inline int add(con(int) a, con(int) b) {return a + b >= MOD ? a + b - MOD : a + b;}
inline int sub(con(int) a, con(int) b) {return a - b < 0 ? a - b + MOD : a - b;}
inline int mul(con(int) a, con(int) b) {return int(1ll * a * b % MOD);}
inline int ina_pow(int a, int b) {
	int r = 1;
	while( b ) {
		if( b & 1 ) r = mul(r, a);
		a = mul(a, a), b >>= 1;
	}
	return r;
}

int n, m;
int f[N][N], bino[N][N];

void init() {
	for(int i=0;i<N;i++) {
		bino[i][0] = 1;
		for(int j=1;j<=i;j++) bino[i][j] = add(bino[i-1][j], bino[i-1][j-1]);
	}
}
int main() {
	init();
	scanf("%d%d", &n, &m);
	// P - x = i
	f[0][0] = 1;
	int k = min(n, m - 2);
	for(int i=1;i<=n;i++) {
		int sum = 0;
		for(int j=1;j<=n;j++) {
			sum = add(sum, f[i - 1][j - 1]);
			if(j - k > 0) sum = sub(sum, f[i - 1][j - k - 1]);
			f[i][j] = sum;
		}
	}
	int ans = ina_pow(m - 1, n), invp = ina_pow(m, MOD-2);
	if( n & 1 ) ans = sub(ans, mul(sub(ans, m - 1), invp));
	else ans = sub(ans, mul(add(ans, m - 1), invp));
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++)
			if( (n - i) % m != j % m && n - i >= j + m )
				ans = sub(ans, mul(mul(f[i][j], m - 1), bino[n][i]));
	printf("%d\n", ans);
	return 0;
}

---

THE END

Thanks for reading!

这万象 恒有道可求
尽人间 穷宇宙
曾邂逅 是告诫亦是悠远的经咒
都化作 万物的风流
总试问 何所有
到尽头 这至简的真言知否

——《万象霜天》By 赤羽

> Link 万象霜天-Bilibili