题解 | #武义寺#

依依寺 的题解里面讲到了一个非常麻烦的公式。这里提供一个我的赛时想出来的简单做法。

对于一个排列，我们单独看待 的所有取值对答案的贡献。

回顾 的定义：

第一个满足 的 就是这个排列的 。

那么，当 刚好产生贡献时，就有两个条件要满足：

直接做显然太麻烦了，我们分开做：

1.

这点很简单。

定义 为 。从后往前考虑每一个数字，易得 。

2.

在处理完 之后，就可以自然而然地得出 的概率为 。

然后就可以计算答案了。

Code:

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

const int kMod = 998244353;

int n, fac[1000010], ivs[1000010], inv[1000010], pbs[1000010], prb[1000010], ans;

int qpow(int x, int y) {
  int rs = 1;
  for(; y; y >>= 1) {
    if(y & 1) {
      rs = rs * x % kMod;
    }
    x = x * x % kMod;
  }
  return rs;
}

int qinv(int x) {
  return qpow(x, kMod - 2);
}

void init() {
  fac[0] = 1;
  for(int i = 1; i <= 1000000; i++) {
    fac[i] = fac[i - 1] * i % kMod;
  }
  ivs[1000000] = qinv(fac[1000000]);
  for(int i = 999999; i >= 0; i--) {
    ivs[i] = ivs[i + 1] * (i + 1) % kMod;
  }
  for(int i = 1; i <= 1000000; i++) {
    inv[i] = ivs[i] * fac[i - 1] % kMod;
  }
}

signed main() {
  init();
  cin >> n;
  pbs[0] = 1;
  for(int i = 1; i <= n; i++) {
    pbs[i] = qpow(n - i + 1, i) * fac[n - i] % kMod * ivs[n] % kMod;
  }
  for(int i = 1; i <= n + 1; i++) {
    prb[i] = (pbs[i - 1] - pbs[i] + kMod) % kMod;
    ans = (ans + i * prb[i]) % kMod;
  }
  cout << ans << '\n';
  return 0;
}