P9823 [ICPC2020 Shanghai R] The Journey of Geor Autumn 题解

· · 题解

思路

注意到题目中的限制条件是 a_i > 一坨东西的 \min，那么可以从 a_i 的最小值入手。因为没有比 1 更小的了，所以 1 一定要填在 [1,k] 这个区间，才能保证序列的合法。

于是考虑 1 的位置，设它在 x。那么对于 [1,x) 就可以没有限制随便填，方案数就是 C_{n - 1}^{x - 1}\times (x - 1)!。对于 (x,n] 的前 k 个位置，你会发现没有限制了！因为最小的 1 已经被填在了 x，不会有比它更小的数了。于是这部分的方案数转化成了一个新的子问题，记其为 f_{n - x}。故总方案数 f_n = \displaystyle\sum\limits_{x = 1}^{\min(n,k)}C_{n - 1}^{x - 1}\times (x - 1)! \times f_{n - x}，相当于做一个 dp 就行了。

但是直接求是 O(nk) 的，需要优化一下。把 C_{n - 1}^{x - 1} 写成 \dfrac{(n - 1) !}{(x - 1)! \times (n - x)!}，(x - 1)! 就被消掉了，再将 (n - 1)! 提到 \sum 外面，得到：f_n = (n - 1)!\displaystyle\sum\limits_{x = 1}^{\min(n,k)}\dfrac{f_{n - x}}{(n - x)!}。这玩意儿用个前缀和维护就行了。

复杂度 O(n)。

code

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int N = 1e7 + 5,mod = 998244353;
int n,k;
ll f[N],sum[N],fac[N],inv[N];
ll qpow(ll x,ll y){
    ll res = 1;
    while(y){
        if(y & 1) res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}
ll C(ll x,ll y){
    if(x < y || x < 0 || y < 0) return 0;
    return fac[x] * inv[y] % mod * inv[x - y] % mod;
}
int main(){
    cin >> n >> k;
    fac[0] = inv[0] = 1;
    for(int i = 1;i <= n;++ i) fac[i] = fac[i - 1] * i % mod;
    inv[n] = qpow(fac[n],mod - 2);
    for(int i = n - 1;i >= 1;-- i) inv[i] = inv[i + 1] * (i + 1) % mod;
    f[0] = sum[0] = 1;
    for(int i = 1;i <= n;++ i){
        f[i] = sum[i - 1];
        if(i - 1 - k >= 0) f[i] = (f[i] - sum[i - k - 1] + mod) % mod;
        f[i] = f[i] * fac[i - 1] % mod;
        sum[i] = (sum[i - 1] + f[i] * inv[i] % mod) % mod;
    }
    cout << f[n];
    return 0;
}