自动搬运

查看原文

来自洛谷，原作者为

	CaiZi 初三蒟蒻 || 坐标 FJ || ENFP-A || MC&PVZ&RS 玩家 || 出题团为 CZOI（80765）

搬运于2025-08-24 23:15:18，当前版本为作者最后更新于2025-02-06 19:34:51，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

观察一下每次施展魔法后 $S_0$ 的变化，可以得到最终答案为：

$$\sum_{i_1=1}^{n}\sum_{i_2=1}^{i_1}\cdots\sum_{i_{m-1}=1}^{i_{m-2}}\sum_{i_m=1}^{i_{m-1}}k^{i_m} $$

考虑用一次等比数列求和公式，得到答案为：

$$\dfrac{\sum_{i_1=1}^{n}\sum_{i_2=1}^{i_1}\cdots\sum_{i_{m-1}=1}^{i_{m-2}}(k^{i_{m-1}+1}-k)}{k-1} $$

拆开括号，得：

$$\dfrac{(\sum_{i_1=1}^{n}\sum_{i_2=1}^{i_1}\cdots\sum_{i_{m-1}=1}^{i_{m-2}}k^{i_{m-1}+1})-k(\sum_{i_1=1}^{n}\sum_{i_2=1}^{i_1}\cdots\sum_{i_{m-1}=1}^{i_{m-2}}1)}{k-1} $$

我们发现前一个括号里面又是一个等比数列求和，可以递归下去继续算，直到算到没有 $\sum$。

然后我们要求出：

$$\sum_{i_1=1}^{n}\sum_{i_2=1}^{i_1}\cdots\sum_{i_{p-1}=1}^{i_{p-2}}\sum_{i_p=1}^{i_{p-1}}1 $$

然后我们不难发现，这个式子等价于值域为 $[1,n]$、长度为 $p$、单调不递增的序列 $\{i_p\}$ 的个数。我们设 $a_j$ 表示 $j$ 在 $\{i_p\}$ 中的出现次数，由于序列 $\{i_p\}$ 单调不递增，所以每个 $\{i_p\},\{a_n\}$ 唯一对应。于是我们可以把问题转化为，求 $\sum_{j=1}^{n}a_j=p$ 的非负整数序列 $\{a_n\}$ 的个数。这是一个典型的插板法问题，答案为 $\dbinom{n+p-1}{p}$。注意 $p=0$ 时值为 $1$。

注意当 $k=1$ 时不能用等比数列求和公式，但本质就是上面的 $p=m$ 的情况，直接输出 $\dbinom{n+m-1}{m}$ 即可。

实际实现时，可以把递归改成递推，避免被卡常。

$O(1)$ 求组合数，时间复杂度为 $O(n+\sum m)$。

代码展示：

#include<bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
int t,n,m,k,fac[4000001],inv[4000001],facinv[4000001],invk1,invk2,ans;
inline int qpow(int a,int b,int c=1){
	while(b){
		if(b&1){
			c=c*a%mod;
		}
		a=a*a%mod;
		b>>=1;
	}
	return c;
}
inline int binom(int a,int b){
	return fac[a]*facinv[b]%mod*facinv[a-b]%mod;
}
signed main(){
	cin.tie(nullptr)->sync_with_stdio(0);
	fac[0]=facinv[0]=inv[1]=1;
	for(int i=2;i<=4000000;i++){
		inv[i]=mod-inv[mod%i]*(mod/i)%mod;
	}
	for(int i=1;i<=4000000;i++){
		fac[i]=fac[i-1]*i%mod;
		facinv[i]=facinv[i-1]*inv[i]%mod;
	}
	cin>>t;
	while(t--){
		cin>>n>>m>>k;
		if(k==1){
			ans=binom(n+m-1,m);
		}
		else{
			invk1=qpow(k,mod-2);
			invk2=qpow(k-1,mod-2);
			ans=qpow(k,n+m);
			k=qpow(k,m);
			for(int i=1;i<=m;i++){
				ans=(ans-binom(n+i-2,i-1)*k%mod+mod)%mod*invk2%mod;
				k=k*invk1%mod;
			}
		}
		cout<<ans<<'\n';
	}
	return 0;
}

最后来玩个游戏吧，把 $n=656,m=960,k=17$ 时的答案写在纸上，快速塞给你同桌并唱出题目背景给出的歌，然后后把同桌的反应分享在评论区（doge）。