Codeforces 886E Maximum Element 组合数学 + dp

时间：2024-10-17 17:34:33

我们定义dp[ i ]表示长度为 i 的序列， 最后没有一个==k的时候返回的方案数， 也就是最后强制返回 i 的方案数。

我们能得到dp方程   dp[ i ] = sum(dp[ i - j - 1 ] * comb(i - 1,  j) * F[ j ])  0 <= j <= k - 1，

然后会发现这个东西不好转移， 我们可以把comb(i - 1,  j) * F[ j ] 这个东西合并一下变成 F(i - 1) / F(i - 1 - j)

然后就变成   dp[ i ] = F(i - 1) * sum(dp[ i - j - 1] / F(i - j - 1))  0 <= j <= k - 1， 然后这个东西存个前缀和就好啦。

有了dp数组之后， 我们就算出最后答案等于 n 的方案数， 从总方案数里面减去就好啦。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PLL pair<LL, LL>

#define PLI pair<LL, int>

#define PII pair<int, int>

#define SZ(x) ((int)x.size())

#define ull unsigned long long

using namespace std;

const int N = 1e6 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = ;

const double eps = 1e-;

const double PI = acos(-);

void add(int &a, int b) {

    a += b; if(a >= mod) a -= mod;

}

int Power(int a, int b) {

    int ans = ;

    while(b) {

        if(b & ) ans = 1LL * ans * a % mod;

        a = 1ll * a * a % mod; b >>= ;

    }

    return ans;

}

int n, k, way, dp[N], prefix[N];

int F[N], Finv[N], inv[N], tmp, ans;

int comb(int n, int m) {

    if(n < m || n < ) return ;

    return 1ll * F[n] * Finv[m] % mod * Finv[n - m] % mod;

}

int main() {

    inv[] = F[] = Finv[] = ;

    for(int i = ; i < N; i++) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;

    for(int i = ; i < N; i++) F[i] = 1ll * F[i - ] * i % mod;

    for(int i = ; i < N; i++) Finv[i] = 1ll * Finv[i - ] * inv[i] % mod;

    scanf("%d%d", &n, &k);

    for(int i = ; i <= k; i++) {

        dp[i] = F[i];

        prefix[i] = (prefix[i - ] + 1ll * dp[i] * Finv[i] % mod) % mod;

    }for(int i = k + ; i <= n; i++) {

        dp[i] = (prefix[i - ] - prefix[i - k - ] + mod) % mod;

        dp[i] = 1ll * dp[i] * F[i - ] % mod;

        prefix[i] = (prefix[i - ] + 1ll * dp[i] * Finv[i] % mod) % mod;

    }

    ans = F[n];

    add(ans, mod - dp[n]);

    for(int i = ; i <= n - k; i++) {

        add(ans, mod - (1ll * comb(n - , i - ) * dp[i - ] % mod * F[n - i] % mod));

    }

    printf("%d\n", ans);

    return ;

}

/*

*/

相关文章