题解：P10116 [LMXOI Round 1] Random

· · 题解

论我是怎么做到一个青题和 AI 自由辩论了一个中午才理解做法的。理解了以后感觉这个题很牛啊，为啥青。

直接做的话，你会发现大概是一个 KMP 自动机上 DP，加上矩阵优化应该可以过除了最后一个子任务的所有点。但是 m=3\times 10^6 就根本没法矩阵加速，所以需要想别的做法。

由于假如我们不要求一个点必须正确，结果就是若干指数乘起来，看起来比较简洁，所以考虑二项式反演。但是直接对 n=10^9 显然没法做，所以需要先减小问题规模。

考察一个性质，由于序列是经过 q 次任意操作生成的，所以每一个可能得生成序列概率是相同的，可以推出，B 在 A 的每一个位置匹配概率也是相同的。所以我们只需要求 B 在 [1,m] 区间内和 A 匹配的方案数，然后乘上 (n-m+1) 就可以了。

接着试图对于 [1,m] 区间内的方案数来做二项式反演。那么需要想明白：钦定什么，以及 f(i) 怎么求。

对于第一个问题，第一想法，大功率是钦定至多 i 个位置相同，或者钦定至少 i 个位置不相同。但是我们发现这么钦定会有问题，因为这些位置的最终值取决于最后一次修改，而不是所有的修改，所以之前可以允许相同的修改。然而最后一次修改的时间又不是一定的，然后你就会发现式子是一个非常复杂的和式，难以优化。

我们发现刚才钦定的问题根源在于，假如单单认为这些位置不相同，那么修改的形态是复杂的。所以需要考虑更强的钦定：钦定这些位置没有被修改过。

那么这样，修改的位置的方案数是容易的，就是 (n-i)^{q}。但是，修改的数值的方案数并不好做。我们不确定我们修改了多少个位置，所以没有办法给这些位置匹配相应的值；假如你枚举这个位置又变成一个难以化简的和式了。

所以来到了本题最妙的一步：我们只钦定修改的位置，对于具体修改的值的计算，外提。这样，我们发现对于所有 m 个位置，值是固定的，也就是最后一次修改需要固定。其余的所有修改，都不需要固定，因此对于单一的操作位置序列，修改的值的方案数就是 k^{q-m}。一定不要把这一步放在 f(i) 中理解，不然组合意义根本不对。

结合一下上面的所有，写成完整式子就是：

(n-m+1)k^{q-m}\sum^{m}_{i=0}(-1)^i\binom{m}{i}(n-i)^q

直接计算即可。时间复杂度 O(m\log q)，空间复杂度 O(m)。

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i ++ )
#define per(i, l, r) for(int i = (l); i >= (r); i -- )
#define endl '\n'
using namespace std;

const int N = 3e6 + 5;
const int MOD = 998244353;
int n, m, q, k, fac[N], inv[N], ans;
void add(int &x, int y) { x += y; if(x >= MOD) x -= MOD; }

int qpow(int x, int b = MOD - 2) {
  if(b < 0) return 0;
  int res = 1;
  for(; b; b >>= 1, x = 1ll * x * x % MOD)
    if(b & 1) res = 1ll * res * x % MOD;
  return res;
}

void init() {
  fac[0] = 1;
  rep(i, 1, m) fac[i] = 1ll * fac[i - 1] * i % MOD;
  inv[m] = qpow(fac[m]);
  per(i, m - 1, 0) inv[i] = 1ll * inv[i + 1] * (i + 1) % MOD;
}

int C(int n, int m) {
  if(n < m) return 0;
  return 1ll * fac[n] * inv[n - m] % MOD * inv[m] % MOD;
}

int main() {
  ios :: sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> m >> q >> k;
  init();
  rep(i, 0, m) {
    int sign = i & 1 ? MOD - 1 : 1;
    add(ans, 1ll * sign * C(m, i) % MOD * qpow(n - i, q) % MOD);
  }
  cout << 1ll * (n - m + 1) * qpow(k, q - m) % MOD * ans % MOD;
  return 0;
}