6

「SOL」Nondivisible Prefix Sums(AtCoder)

 2 years ago
source link: https://luckyglass.github.io/2021/21Apr16thArt4/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

「SOL」Nondivisible Prefix Sums(AtCoder)

发表于

2021-04-16 分类于 OI题解

热度： 10 Valine： 0

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

给定正整数 n 以及质数 p，求有多少个数列 a1,a2,⋯,an，满足

  • 1≤ai≤p；
  • 存在一种将 {ai} 重新排列为 {bi} 的方案，使得 ∀i∈[1,n],∑j=1ibjmodp≠0，换句话说，不存在 b 的前缀和是 p 的倍数。

数据规模：1≤n≤5000，2≤p≤108。

如果 ∑aimodp=0，一定不满足条件，先把这个情况给排除。也就是说下面的解析都在 ∑ai≢0 的前提条件下。

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

cr≤∑i=1n[ai≠r](p−ai)+p−1=∑i≠r(p−i)ci+p−1

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

考虑证明这个结论。

需要判断是否存在满足条件的 {ai} 的重排 {bi}，不妨从后往前决策 bi 是哪一个数。

可以理解成这样一个过程：从数轴上的 ∑ai 位置出发，每一步可以向负方向走 bi 的距离，不可以经过 p 的倍数的点。

反证，若 c1>∑i>1(p−i)ci+p−1，即 c1≥p+∑i>1(p−i)ci，移项可得 ∑i=1ici≥p+∑i>1pci⇒∑ai≥p(1+∑i>1ci)

要从数轴上 ∑ai 回到原点，中间会**跨过** ⌊∑aip⌋ 个 p 的倍数点，根据上面的分析，这样的倍数点有大于等于 (1+∑i>1ci) 个，而要跨过这些点，必须要走距离大于 1 的一步，可以理解成「消耗」一个大于 1 的 ai。

这就要求大于 1 的 ai 的数量大于等于需要跨过的点的数量，而 ∑i+1ai 是严格小于跨过的点数的，所以这样的 {ai} 一定不满足条件。必要性成立。

若 {ai} 满足条件，构造一种方案以证明其充分性。初始的序列 {bi} 为空，考虑每次在末尾加入当前剩余数量最多的元素 x：

- 若加入后前缀和不是 p 的倍数，则合法； - 否则加入另一个数 y。

如果这样构造不合法，即只剩下 x 但是 x 不能加入当前数列。并且剩下的 x 至少有两个，否则 p∣∑ai。

这意味着 x **一直是**剩余数量最多的元素。若存在某个时刻 y 的剩余数量超过 x，则在之后的构造中，y 与 x 的剩余数量之差始终不超过 1，不可能最后剩下两个及以上的元素。

换句话说，在我们最初的假设中，x 就是 1。

那么我们可以观察一下这样构造出来的数列长什么样，大概是： 1,1,…,1⏞p−1,at1,1,1,…,1⏞p−at1,at2,1,1,…,1⏞p−at2,at3,…

什么时候会不合法呢？就是当所有大于 1 的 ai 都放完后还剩余了 1，那么此时 1 的数量应严格大于 (p−1)+∑ai>1(p−ai)，与结论的条件不符。故这样构造一定合法，充分性得证。

考虑简单容斥，从所有满足 p∤∑ai 的 {ai} 中减去不符合上述结论的。

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

f(i,j)=∑k=1min{p−1,j}f(i−1,j−k)

那么不符合结论的 {ai} 则为

∑cnt∑sum[n−cnt≢sum][n−cnt≥p+sum]f(cnt,sum)(ncnt)(p−1)

组合数 (ncnt) 即插入 1 的方案数，再乘上 (p−1) 是因为我们默认了出现次数最多的是 1，实际上 1∼p−1 都可以。

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

所以只需进行一个状态数是 O(n2) 的 DP，经过前缀和优化可以 O(1) 转移。

总复杂度 O(n2)。

/*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


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK