C - Sequence Scores

题意

$1$ 以上 $M$ 以下の整数から成る長さ $N$ の数列 $A$ に対して、$f(A)$ を以下のように定義します。

• 長さ $N$ の数列 $X$ があり、初め全ての要素は $0$ である。$f(A)$ を、次の操作を繰り返して $X$ を $A$ に等しくするための最小の操作回数とする。
  • $1\le l\le r\le N$ と $1\le v\le M$ を指定する。$l\le i\le r$ に対して $X_i$ を $\max(X_i,v)$ で置き換える。

$A$ として考えられる数列は $M^N$ 通りあります。これら全ての数列に対する $f(A)$ の和を $998244353$ で割った余りを求めてください。

解析

显然，填充 $v$ 这个值要花费的次数，就是将原数列中所有大于 $v$ 的元素去掉，再按顺序拼接起来得到的数列中 $v$ 的段数。也就是说，我们只关心大于 $v$ 的值出现了多少次，而不关心这些值出现的位置。

设 $dp_i$ 表示 $v$ 和小于 $v$ 的值占用 $i$ 个位置时的所有情况中填充 $v$ 花费的次数的总和。则所有数列中填充 $v$ 花费的次数的总和为

$$\sum_{i=1}^N\binom{N}{N-i}(M-i)^{N-i}dp_i$$

如果我们能对每个 $v$ 在 $O(N)$ 时间内求出 $dp_i$，就能 $O(NM+N^2)$ 求出答案了。设 $f_{i,0/1}$ 表示占用 $i$ 个位置，且最后一个位置是/否为 $v$ 的所有方案中填充 $v$ 次数的总和，而 $g_{i,0/1}$ 表示占用 $i$ 个位置，且最后一个位置是/否为 $v$ 的方案数。则

$$\begin{aligned} f_{i,0}&=(v-1)(f_{i-1,0}+f_{i-1,1})\\ f_{i,1}&=(f_{i-1,0}+g_{i-1,0})+f_{i-1,1}\\ g_{i,0}&=(v-1)(g_{i-1,0}+g_{i-1,1})\\ g_{i,1}&=g_{i-1,0}+g_{i-1,1} \end{aligned}$$

这是因为，从 $f_{i-1,0}$ 向 $f_{i,1}$ 转移时，$v$ 的段数增加了 $1$，则之前的每种方案都要多填充 $1$ 次，于是要加上 $g_{i-1,0}$。

实现

#include <bits/stdc++.h>

typedef long long int ll;
const int maxn = 5e3 + 19, mod = 998244353;

int qpow(int a, int b){
    int res = 1;
    while(b){
        if(b & 1) res = (ll)res * a % mod;
        a = (ll)a * a % mod, b >>= 1;
    }
    return res;
}

int fact[maxn], ifact[maxn];

void exgcd(int a, int b, int &x, int &y){
    if(!b) return (void)(x = 1, y = 0);
    exgcd(b, a % b, y, x), y -= a / b * x;
}

void init(int n){
    fact[0] = 1;
    for(int i = 1; i <= n; ++i)
        fact[i] = (ll)fact[i - 1] * i % mod;
    exgcd(fact[n], mod, ifact[n], ifact[n - 1]);
    for(int i = n - 1; i >= 0; --i)
        ifact[i] = (ll)ifact[i + 1] * (i + 1) % mod;
}

inline int binom(int n, int m){
    return (ll)fact[n] * ifact[n - m] % mod * ifact[m] % mod;
}

int n, m;
int f[maxn][2], g[maxn][2];

int main(){
    std::scanf("%d%d", &n, &m), init(n);
    int ans = 0;
    for(int i = 1; i <= m; ++i){
        f[0][0] = 0, g[0][0] = 1;
        for(int j = 1; j <= n; ++j){
            f[j][1] = (f[j - 1][1] + (ll)f[j - 1][0]) % mod;
            f[j][0] = (f[j - 1][1] + (ll)f[j - 1][0]) * ll(m - i) % mod;
            f[j][1] = (f[j][1] + g[j - 1][0]) % mod;

            g[j][1] = (g[j - 1][1] + (ll)g[j - 1][0]) % mod;
            g[j][0] = (g[j - 1][1] + (ll)g[j - 1][0]) * ll(m - i) % mod;
        }
        for(int j = 1; j <= n; ++j)
            ans = (ans + (ll)binom(n, n - j) * qpow(i - 1, n - j) % mod * (f[j][0] + f[j][1])) % mod;
    }
    std::printf("%d\n", ans);
}

来源

AtCoder Regular Contest 114 C - Sequence Scores

评论