题解：P10116 [LMXOI Round 1] Random

原题链接

• 洛谷 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;
}