题解：P10116 [LMXOI Round 1] Random

· · 题解

题意简述

初始时，长度为 n 的序列全为 0。

进行 q 次操作：每次可以选择一个位置，将其改为 [1,k] 范围内的任意一个数。

给定一个长度为 m 的匹配序列 B\in[1,k]^m，统计在所有可能的 (nk)^q 个结果序列中，序列 B 出现的总次数。

解题思路

我们注意到答案与 B 无关。固定一个长度为 m 的窗口，窗口总数为：

n-m+1

若窗口内漏掉 i 个格子，则可选位置为 n-i，对应下标序列数为 (n-i)^q，因此有：

\sum_{i=0}^{m}(-1)^i\binom{m}{i}(n-i)^q

在覆盖成立时，为使窗口最终等于给定 B，这 m 个格子的最后一次写入被唯一确定，其余 q-m 次任意，因子为：

k^{q-m}

综上，最终答案为：

(n-m+1)\cdot k^{q-m}\cdot\sum_{i=0}^{m}(-1)^i\binom{m}{i}(n-i)^q

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int mod=998244353;
const int N=3000005;
ll inv[N],fac[N],jv[N];
void init()
{
    fac[0]=jv[0]=1;
    for(int i=1;i<N;i++)
    {
        inv[i]=i==1?1:(mod-mod/i)*inv[mod%i]%mod;
        fac[i]=fac[i-1]*i%mod;
        jv[i]=jv[i-1]*inv[i]%mod;
    }
}
ll C(ll n,ll m)
{
    if(n<m||m<0)return 0;
    return fac[n]*jv[n-m]%mod*jv[m]%mod;
}
ll Pow(ll x,ll y)
{
    x%=mod;
    ll res=1;
    while(y)
    {
        if(y&1)res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    ll n,m,q,k,a,b;
    cin>>n>>m>>q>>k>>a>>b;
    if(q<m)
    {
        cout<<0<<'\n';
        return 0;
    }
    ll sum=0;
    for(int i=0;i<=m;i++)
    {
        sum=(sum+Pow(-1,i)*C(m,i)%mod*Pow(n-i,q)%mod)%mod;
    }
    ll ans=sum*Pow(k,q-m)%mod*(n-m+1)%mod;
    cout<<(ans%mod+mod)%mod<<'\n';
    return 0;
}