Solution-P12405
CaiZi
·
·
题解
观察一下每次施展魔法后 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} 即可。
实际实现时，可以把递归改成递推，避免被卡常。
代码展示：
```cpp
#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）。