[ARC133E] Cyclic Medians 题解

JiaY19 / 2024-11-10 / 原文

一点不会套路。

思路

对于中位数相关，发现我们不好直接表示与中位数有关的内容。

不妨枚举 $x$，把大于 $x$ 的标为 $1$，小于等于 $x$ 的标为 $0$，这样把所有最终为一的方案数加起来就是原来的答案。

大概是这样一个东西：

\[k=\sum_{i=0}^k [i<k] \]

这个怎么求呢。

发现若一组 $(x,y)$ 是 $(1,1)$ 或者是 $(0,0)$ 的话，后面的东西就与 $a$ 无关了。

继续思考，在 $x=i$ 与 $x=v-i$ 的时候，出现 $(0,0)$ 的概率和 $(1,1)$ 的概率恰好是相反的。

这告诉我们，我们只需要求出只出现 $(0,0)$ 与 $(1,1)$ 的方案，在这些方案中，最后为 $1$ 与最后为 $0$ 的概率是相等的。

所以我们只要求出只出现 $(0,0)$ 与 $(1,1)$ 的方案。

这个也不好求。

使用容斥，我们求出每一组 $(x,y)$ 都要求 $x\not =y$ 的方案。

这个东西依据经典结论，这个两个序列各会被分成 $\gcd(n,m)$ 份，每一份都要求相等，并且与另一个序列是一一对应的关系。

所以当你枚举 $x$ 的时候，方案数为：

\[(x^\frac{n}{g}(v-x)^\frac{m}{g}+(v-x)^\frac{n}{g}x^\frac{m}{g})^g \]

其中，$g=\gcd(n,m)$。

然后就做完了。

时间复杂度：$O(v\log n)$。

Code

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int mod = 998244353;

int n, m, v, a, g;

inline int power(int x, int y) {
  int res = 1;
  while (y) {
    if (y & 1) res = res * x % mod;
    x = x * x % mod, y >>= 1;
  }
  return res;
}

signed main() {
  cin >> n >> m >> v >> a, g = __gcd(n, m);
  int sm = power(v, n + m);
  int ns = 0;
  n /= g;
  m /= g;
  for (int i = 0; i <= v; i++) {
    int nm = 0;
    nm += power(i, n) * power(v - i, m);
    nm += power(v - i, n) * power(i, m);
    nm = power(nm % mod, g);
    if (a > i) ns = ns + nm;
    int cr = sm - nm;
    if (cr < 0) cr += mod;
    if (cr & 1) cr += mod;
    cr = cr / 2;
    ns = ns + cr;
  }
  cout << ns % mod << "\n";
}