题解 CF1861E Non-Intersecting Subpermutations

BrainLE · 2023-10-10 12:51:02 · 题解

原题链接

给一个简单易懂的容斥做法。

思路

对每个序列都计算合法段的个数比较困难，可以考虑计算以每个 i 为结尾的合法段的贡献，求和即答案。

设 f_i 表示只考虑前 i 个位置，以 i 为结尾的合法段的贡献次数。因为重叠不会有贡献，因此对于一个已确定的序列，计算答案一定是贪心选尽可能靠前的段。如果不考虑重叠不计的限制，f_i 就是 k! \times k^{i-k}。

现在减去不合法的，这种情况等价于存在一个 [i-k+1,i) 中的 j，使得 j 为结尾的段合法且被计算贡献，这个方案数就是 f_j \times (i-j)!。乘 (i-j)! 是由于 [i-k+1,i] 这个段中 1 到 k 各出现一次，而 [i-k+1,j] 中的数已经被以 j 为结尾的段确定了，剩下 i-j 个数任意指定次序。

因此，有 f_i = k! \times k^{i-k} - \sum\limits_{i-k+1\le j<i} f_j \times (i-j)!，后面的 n-i 个数随便选，因此答案是 \sum\limits_{i=k}^{n} f_i \times k^{n-i}。

这个做法有 O(nk) 的时间复杂度和 O(n) 的空间复杂度。

代码

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define db double
#define gc getchar
#define pc putchar
#define fs first
#define sc second
#define pii pair<int,int>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define lowbit(x) (x&(-x))
using namespace std;

ll read()
{
    ll x=0,f=1;
    char ch=gc();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=gc();
    }
    while(ch>='0'&&ch<='9')
        x=x*10+(ch^48),ch=gc();
    return x*f;
}
void print(ll x)
{
    if(x<0)pc('-'),x=-x;
    if(x>9)print(x/10);
    pc(x%10+48);
}

const int N=4005;
const ll mod=998244353;
int n,k;
ll fac[N],f[N];

ll qpow(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1)res=res*a%mod;
        a=a*a%mod,b>>=1;
    }
    return res;
}
void init()
{
    fac[0]=1;
    for(int i=1;i<=n;i++)
        fac[i]=fac[i-1]*i%mod;
}

int main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);

    n=read(),k=read(),init();

    for(int i=k;i<=n;i++)
    {
        f[i]=fac[k]*qpow(k,i-k);
        for(int j=i-k+1;j<i;j++)
            f[i]-=f[j]*fac[i-j]%mod;
        f[i]=(f[i]%mod+mod)%mod;
    }

    ll ans=0;
    for(int i=k;i<=n;i++)
        ans=(ans+f[i]*qpow(k,n-i))%mod;
    print(ans);

    return 0;
}