自动搬运

查看原文

来自洛谷，原作者为

	int08 学生 Div.1 rk 900||Day after day after day we fly, past the moon and the sun and we don't know why...

搬运于2025-08-24 22:54:50，当前版本为作者最后更新于2024-01-29 10:29:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前言

不知道 Random 是不是指一首曲子。

有趣但是简单的数数题，感觉比 T2 简单。

都推式子？那我就从组合意义考虑吧！

Solution

考虑我们在统计 $B$ 在操作完的所有可能序列中的出现次数，这个是很烦的，比如：

$$A=[1,2,1,2,1],B=[1,2,1]$$

发现有重叠部分，但是事实上这里对答案的贡献为 $2$，这是不好快速统计的。

如果考虑操作序列去匹配 $B$ 来更新答案是困难的，那么正难则反，考虑 $B$ 序列要出现在某一位置能匹配多少种操作序列。

为什么这是正确的？

因为同一个操作序列中如果多次出现 $B$ 要多次更新答案，反过来在多个位置匹配到同一个操作序列，也会多次更新答案，而且次数相等。

这时候我们惊喜地发现两件事：

第一、$B$ 序列出现在任意位置匹配的操作序列数相等，因为每次操作选择任意位置的概率相等。

所以我们只需要计算 $B$ 出现在 $[1,m]$ 的情况，乘上 $(n-m+1)$ 即可。

第二、类似的，$B$ 序列每个数具体是啥，对答案没有影响，因为修改位置是独立的，我修改某一个位置影响不到别的位置，而且修改为每个数的概率也相等。

所以我们压根不用输入第二行。

那么现在，修改的位置选择共 $n^q$ 种情况，修改成的数有 $k^q$ 种情况，分开计算，再乘起来即可。

修改成的数

要求：对应的 $m$ 个位置最后一次出现的时候必须修改成对应的数。

换句话说，不管我前面的修改位置怎么选，总有 $m$ 个操作我的修改成的数是固定的，而剩下的，要么修改位置大于 $m$ 我压根不管（我只统计 $B$ 出现于 $[1,m]$ 的答案）、要么后面这个位置还要改对，总之我想改成哪个数无所谓。

共有 $1^m\times k^{q-m}$ 中合法情况。

修改位置

要求：$1$ 到 $m$ 每个位置至少被选中过一次。

有多少种情况？我又不会了。

老规矩考虑正难则反，我统计不是每一个位置都出现过的情况。

即：我考虑有 $i$ 个位置没有出现过，选择这 $i$ 个位置有 $\binom{m}{i}$ 种选法，然后每次选位置，除了这 $i$ 个位置皆可选，共 $(n-i)^q$ 种情况。

然后用小学学过的容斥原理，$i$ 为奇数时减去，$i$ 为偶数时加上，就结束了。

最后，答案为：

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

式子和其他题解有一点不同。

实现是简单的，$\binom{m}{i}$ 递推，逆元用快速幂实现。

后记

听我劝谏：人生苦短，正难则反……

Play like you never did before!

AC code

#include<bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
int qp(int x,int y)
{
	int ans=1;
	for(int i=1,j=x;i<=y;i*=2,j=(j*j)%mod) if(y&i) ans=(ans*j)%mod;
	return ans;
}
int n,m,q,k,i,j,c[3141592],ans,anf;
signed main()
{
	cin>>n>>m>>q>>k;
	if(q>=m)
	{
		ans=((n-m+1)*qp(k,q-m))%mod;
		anf=qp(n,q);
		c[1]=c[m-1]=m;c[0]=c[m]=1;
		for(i=2;i<=(m+1)/2;i++) c[i]=c[m-i]=((c[i-1]*(m+1-i))%mod*qp(i,mod-2))%mod;
		for(i=1;i<=m;i++)
		{
			if(i%2)
				anf=(anf-qp(n-i,q)*c[i])%mod;
			else
				anf=(anf+qp(n-i,q)*c[i])%mod;
		}
		anf=(anf+mod)%mod;
		ans=(ans*anf)%mod;
	}
	cout<<ans;
	return 0;
}