U63113:入侵 – 又名 「XG 的数学题」

题目背景

众所周知,XG_Zepto 是一位来自 FZOI 的神仙。他觉得眼下的比赛太简单了,就用扫雷的时间出了一道数学题给 kal0rona。kal0rona 太菜了,看不懂题也不会写,之后求救于你了。

题目思路

很好的一道计数 DP,出自神仙组长 XG_Zepto 之手。首先,设\(f[i][j]\)为长度为\(i\),换弹次数为\(j\)时满足条件的排列数量。之后,考虑枚举第\(i\)个数字出现的位置\(k\),对于位置\(k\)后面的数字是不会有特殊贡献的(贡献为\((i-k)!\)),而对于前面的数,可以进行枚举前一段进行转移,一共有\({k-1}\choose{i-1}\)种选数字的方案和\(f[i-1][j-1\)种排列,乘起来即可,也就是:

\[ F[i][j] = \sum_{k = 1}^{i}f[k-1][j-1]* {{k-1} \choose {i-1}} *(i-1)! \]

可以化简,并用前缀和优化:

\[ F[i][j] = (i-1)!\sum_{k=1}^{i}\frac{f[k-1][j-1]}{(k-1)!} \]

代码

// U63113.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 5050, mod = 998244353;
ll f[MAX_N], prefix[MAX_N], level[MAX_N], inv[MAX_N], n, m;
ll quick_pow(ll bas, ll tim)
{
    ll ans = 1;
    while (tim)
    {
        if (tim & 1)
            ans = ans * bas % mod;
        bas = bas * bas % mod;
        tim >>= 1;
    }
    return ans;
}
int main()
{
    scanf("%lld%lld", &n, &m);
    level[0] = 1, inv[0] = 1;
    for (int i = 1; i <= n; i++)
        level[i] = level[i - 1] * i % mod;
    inv[n] = quick_pow(level[n], mod - 2);
    for (int i = n; i >= 1; i--)
        inv[i - 1] = inv[i] * i % mod;
    for (int i = 0; i <= n; i++)
        prefix[i] = 1;
    for (int j = 1; j <= m; j++)
    {
        for (int i = j; i <= n; i++)
            f[i] = prefix[i - 1] * level[i - 1] % mod;
        for (int i = j; i <= n; i++)
            prefix[i] = f[i] * inv[i] % mod;
        for (int i = j + 1; i <= n; i++)
            prefix[i] = (prefix[i] + prefix[i - 1]) % mod;
    }
    printf("%lld", f[n]);
    return 0;
}

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注