【ARC133E】Cyclic Medians（数学）

Cyclic Medians

题目链接：ARC133E

题目大意

给你四个数 n,m,v,a，然后你可以选择两个长度分别为 n,m，值域在 1~v 之间的数组 x,y。
有一个数 A 初始值为 a，然后进行 nm 次变换，第 i 次把 A,x[(i-1)%n+1],y[(i-1)%m+1] 的中值作为新的 A。
问你对于每一对可能的数组 x,y，求 A 的最终值的和。

思路

直接求不好搞，考虑对于每个 $k$ 求有多少种情况的贡献 $⩾k$。
那 $⩾k$ 的数变成 $1$，$<k$ 的数变成 $0$。

于是只有 $0,1$ 问题看上去似乎可以做了。
发现如果 $(a,0,0)$ 或者 $(a,1,1)$ 这种出现了，那就跟 $a$ 没关系了。
我们就只需要看看最后是 $0$ 还是 $1$。
然后其实有一个东西叫做对称性，就是 $k=p$ 的时候 $0$ 的个数和 $k=v-p$ 的时候 $1$ 的个数是一样的。
而 $k$ 等于啥的时候贡献都是 $1$，所以我们只需要求出所有 $k$ 跟 $a$ 无关的情况数，除二即可。

接着考虑数跟 $a$ 有关的情况数，无关的数量可以用全部减去有关的。
那就是全程都是 $(a,0,1)$ 这种。
那因为有循环，所以独立的行和列只有 $\gcd (n,m)$ 个。
别的会因为能匹配到而要求相同。（匹配你把所有左侧点的 $(i-1)\%n+1$，跟右侧点的 $(i-1)\%m+1$ 连边， 表示这些之间要不同）
（然后由于是二分图，一个连通块中左侧点和右侧点分别都要一样，而且互相之间还要不同，所以是固定了）
然后再根据谁是 $0$ 谁是 $1$，能统计方案：
$(k^{n/\gcd }(v-k{)}^{m/\gcd }+(v-k{)}^{n/\gcd }{k}^{m/\gcd }{)}^{\gcd }$
（里面每一组可以选的，然后有 $\gcd$ 组独立的）

然后就好啦。

代码

#include
#define ll long long
#define mo 998244353

using namespace std;

int n, m, v, a, g;
ll ans;

ll gcd(ll x, ll y) {
	if (!y) return x;
	return gcd(y, x % y);
}

ll ksm(ll x, ll y) {
	ll re = 1;
	while (y) {
		if (y & 1) re = re * x % mo;
		x = x * x % mo; y >>= 1;
	}
	return re;
}

int main() {
	scanf("%d %d %d %d", &n, &m, &v, &a); g = gcd(n, m);
	
	ll all = ksm(v, n + m), inv2 = (mo + 1) / 2;
	ans += all;
	for (int lim = 2; lim <= v; lim++) {
		ll num_no = ksm((ksm(lim - 1, n / g) * ksm(v - lim + 1, m / g) % mo + ksm(v - lim + 1, n / g) * ksm(lim - 1, m / g) % mo) % mo, g);
		if (a >= lim) (ans += num_no) %= mo;
		ll num_yes = (all - num_no + mo) % mo;
		(ans += num_yes * inv2 % mo) %= mo;
	}
	printf("%lld", ans);
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38