CZOI-R3 星光闪耀
hyk2019
·
·
题解
\gdef\mat#1#2{\begin{pmatrix}#1\\#2\end{pmatrix}}
upd：由于赛后发现了捷径，将 k=1 更换为简便解法。
部分分：
正解：巧妙的推式子。
这里先假设 k\ge2。
一个大小为 v 的星团，会生出大小为 1\sim v-1 之间所有整数的星团。按照题目的要求，我们最终要求所有星团的闪耀度之和，而一个星团的闪耀度是 k^v。想一想，一次操作后会对星团的闪耀度之和有什么影响？
k^v\rightarrow\sum_{i=1}^{v-1}k^i
右边是等比数列，如何求和？
\sum_{i=1}^{v-1}k^i=(\sum_{i=0}^{v-1}k^i)-1=\frac{k^v-1}{k-1}-1
如果 u_{a,i} 表示经过 a 次操作后大小为 i 的星团的数量，那么闪耀度之和 S_a 可以看成什么？
S_a=\sum_{i=1}^nu_{a,i}\times k^i
如何转移到 S_{a+1}？
\begin{aligned}
S_{a+1}
&=S_a+\sum_{i=1}^nu_{a,i}\times (\frac{k^i-1}{k-1}-1)\\
&=S_a+\frac1{k-1}\times((\sum_{i=1}^nu_{a,i}\times k^i)-(\sum_{i=1}^nu_{a,i}))-(\sum_{i=1}^nu_{a,i})\\
&=S_a+\frac{S_a-T_a}{k-1}-T_a
\end{aligned}
上面的 T_a=\sum_{i=1}^nu_{a,i} 表示的就是星团个数。
$u_{a,i}$ 的递推规则如下：
$$
u_{a,i}=\sum_{j=i}^nu_{a-1,j}
$$
如何将其简化？
当 $a>0$ 时：
$$
u_{a,i}=\begin{cases}1&i=n\\u_{a-1,i}+u_{a,i+1}&1\le i<n\end{cases}
$$
当 $a=0$ 时：
$$
u_{0,i}=\begin{cases}1&i=n\\0&1\le i<n\end{cases}
$$
实际上，当 $a=1$ 时，$u_{1,i}=1$。所以接下来的这一部分看着很像杨辉三角？
这样，当 $a\ge1$ 时，就可以进一步将递推公式简化成通项公式：
$$
u_{a,i}=\mat{a+n-i-1}{a-1}
$$
因为每一个星团在下一次操作中都要生成一个大小为 $1$ 的星团（包括自己），所以：
$$
T_{a}=u_{a+1,1}=\mat{a+n-1}a
$$
如果赛时不会推式子，也可以打表，可以得出同样的结论。
---
$T_a$ 解决了，$S_a$ 也解决了，那么整条思路就打通了。
我们已知 $S_0=k^n$，接下来只要根据公式 $S_{a+1}=S_a+\frac{S_a-T_a}{k-1}-T_a$ 和 $T_{a}=\mat{a+n-1}a$ 转移到 $a=m$ 即可。
预处理每个数的逆元，最终时间复杂度 $O(\sum m)$。
---
```cpp
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 998244353;
int T, N, M;
long long K, I[4000006], F[4000006];
long long power(long long x, long long y) {
if(y == 0)
return 1;
if(y == 1)
return x;
long long w = power(x * x % MOD, y >> 1);
if(y & 1)
return w * x % MOD;
else
return w;
}
int main() {
F[0] = 1;
int U = 4000005;
for(int i = 1; i <= U; i ++)
F[i] = F[i - 1] * i % MOD;
I[U] = power(F[U], MOD - 2);
for(int i = U - 1; i; i --)
I[i] = I[i + 1] * (i + 1) % MOD;
I[0] = 1;
scanf("%d", &T);
while(T --) {
scanf("%d%d%lld", &N, &M, &K);
if(K == 0) {
puts("0");
continue;
}
long long w = power(K, N), inv = power(K - 1, MOD - 2), C = 1;
for(int i = 1; i <= M; i ++) {
if(K > 1)
w = ((w + (w - C) * inv - C) % MOD + MOD) % MOD;
C = F[N + i - 1] * I[i] % MOD * I[N - 1] % MOD;
}
printf("%lld\n", K == 1 ? C : w);
}
return 0;
}
```