套路题不会做!套路题不会做!套路题不会做!套路题不会做!套路题不会做!
处理中位数的套路就将大于等于 \(k\) 的设置为 \(1\),小于 \(k\) 的设置为 \(0\)。我们要求中位数的和,其实就是对于每一个 \(k\),求中位数 \(\ge k\) 的方案数的和。
没人喜欢 \([1, V]\),我们先改成 \([0, V - 1]\)。考虑三个数的 \(0, 1\) 中位数有什么情况:
- \((a, 0, 0) \to 0\);
- \((a, 1, 1) \to 1\);
- \((a, 0, 1) \to a\)。
发现如果中途出现了前两种情况,那么最后的中位数就与 \(a\) 没有关系了。我们将出现前两种情况的方案和不出现的方案分别计算。
如果出现了,我们发现,根据对称性,如果对于某个 \(k\) 答案为 \(0\),那么对于 \(v - k\) 答案为 \(1\)。那么显然,最后答案等于 \(1\) 的方案数就是总方案数的一半。
考虑没出现的情况,那么我们实际上就是要满足 \(a_{i \bmod n} \ne b_{i \bmod m}\)。设 \(g = \gcd(n, m)\),那么其实就是 \(a_{i} = a_{i + g} = a_{i + 2g} = \cdots, b_{i} = b_{i + g} = b_{i + 2g} = \cdots, a_{i} \ne b_{i}\)。
那么要不然 \(a\) 全选 \(0\)、\(b\) 全选 \(1\),要不然反过来。选 \(0\) 的方案数为 \(k\),选 \(1\) 的方案数为 \(v - k\),那么方案数就是:
\[\left(k^{n/g} (v-k)^{m/g} + k^{m/g} (v-k)^{n/g}\right)^g \]对于这种情况,最后中位数就是 \(a\),那么统计 \(a \ge k\) 的方案即可。
除掉这个就是前一种情况,拿 \(v^{n+m}\) 减去上式然后除以 \(2\) 就是前一种情况的方案数。
然后计算即可。
#include <bits/stdc++.h>
using namespace std;
const int P = 998244353;
int qpow(int a, int b) {
int ans = 1;
while (b) {
if (b & 1) ans = 1ll * ans * a % P;
a = 1ll * a * a % P;
b >>= 1;
}
return ans;
}
int n, m, v, a;
int main() {
scanf("%d%d%d%d", &n, &m, &v, &a);
a--;
int g = __gcd(n, m);
int ans = 0;
for (int k = 0; k <= v; k++) {
int w = qpow((1ll * qpow(k, n / g) * qpow(v - k, m / g)
+ 1ll * qpow(k, m / g) * qpow(v - k, n / g)) % P, g);
ans = (ans + 1ll * (qpow(v, n + m) - w + P) * ((P + 1) / 2)) % P;
if (a >= k) ans = (ans + w) % P;
}
printf("%d\n", ans);
return 0;
}
标签:方案,那么,Cyclic,int,Medians,ARC133E,中位数,套路,ans
From: https://www.cnblogs.com/apjifengc/p/17156462.html