2023 CCPC 华为云计算挑战赛 D-塔

首先先来看第一轮的
假如有n个,每轮那k个

他们的高度的可能性分别为

 n 1/C(n,k)

n+1 C(n-(k-1+1),1)/C(n,k)

n+2 C(n-(k-2+1),2)/C(n,k)

n+i C(n-(k-i+1,i)/C(n,k)

通过概率和高度算出第一轮增加的期望

然后乘上m轮增加的高度加上初始高度，就是总共增加的高度

下面是题解写的过程

 

 

const int inf = 0x3f3f3f3f3f3f3f3f, N = 2e5 + 5, mod = 998244353;
int qpow(int a, int b) {int res = 1;while (b) {if (b & 1) res = res * a % mod;b >>= 1;a = a * a % mod;}return res;
}
int fpow(int x, int r) {int result = 1;while (r) {if (r & 1)result = result * x % mod;r >>= 1;x = x * x % mod;}return result;
}namespace binom {int fac[N], ifac[N];int __ = [] {fac[0] = 1;for (int i = 1; i <= N - 5; i++)fac[i] = fac[i - 1] * i % mod;ifac[N - 5] = fpow(fac[N - 5], mod - 2);for (int i = N - 5; i; i--)ifac[i - 1] = ifac[i] * i % mod;return 0;}();inline int C(int n, int m) {if (n < m || m < 0)return 0;return fac[n] * ifac[m] % mod * ifac[n - m] % mod;}inline int A(int n, int m) {if (n < m || m < 0)return 0;return fac[n] * ifac[n - m] % mod;}
}
using namespace binom;//求解排列组合
signed main() {ios_base::sync_with_stdio(0);cin.tie(0), cout.tie(0);int T;cin >> T;while (T--) {int n, m, k;cin >> n >> m >> k;int fen = qpow(C(n, k), mod - 2);int ans = 0;
//		cout << C(3, 3) << '\n';ans = (ans + n * fen) % mod;for (int i = 1; i <= k; i++) {
//			cout << "------\n" << n - (k - i)-1 << ' ' << (k-i) << "\n" << "---------\n";
//			cout << C(n - (k - i) - 1, i) << '\n';ans = (ans + ((n+i) * fen) % mod * C(n - (k - i+1), i) % mod) % mod;}int w = (ans - n + mod) % mod;cout << (n + w * m % mod) % mod << '\n';}
}