幼儿园篮球题¶
题意¶
蔡徐坤将会进行 S 场巡回篮球演出。由于他高超的技巧，蔡徐坤投没气的球一定能进，投有气的球一定不能进。
在第 i 场演出，场上会有 n_i 个蔡徐坤篮球，其中有 m_i 个是没气的，n_i-m_i 个是有气的。蔡徐坤会随机选择 k_i 个篮球投，若他投进了 x 个球，则该场演出的失败度为 x^L。求演出的期望失败度。
解析¶
对于每场表演，不难发现答案就是
\sum_{i=0}^ki^L\binom{m}{i}\binom{n-m}{k-i}
这样我们可以 O(SN) 回答询问，只能获得暴力分。考虑第二类斯特林数和幂的关系恒等式
n^m=\sum_{i=0}^n\binom{n}{i}\begin{Bmatrix}m\\i\end{Bmatrix}i!
这个恒等式的组合意义是，将 m 个有标号小球放入 n 个有标号盒子的方案数。用该式展开答案
\sum_{i=0}^k\binom{m}{i}\binom{n-m}{k-i}\sum_{j=0}^i\binom{i}{j}\begin{Bmatrix}L\\j\end{Bmatrix}j!
交换枚举顺序并展开二项式系数
\begin{aligned}
&\sum_{i=0}^k\begin{Bmatrix}L\\i\end{Bmatrix}i!\sum_{j=i}^k\dfrac{m!}{(j-i)!i!(m-j)!}\binom{n-m}{k-j}\\
&=\sum_{i=0}^k\begin{Bmatrix}L\\i\end{Bmatrix}m!\sum_{j=i}^k\dfrac{1}{(j-i)!(m-j)!}\binom{n-m}{k-j}\\
&=\sum_{i=0}^k\begin{Bmatrix}L\\i\end{Bmatrix}m!\sum_{j=0}^{k-i}\dfrac{1}{j!(m-j-i)!}\binom{n-m}{k-j-i}\\
&=\sum_{i=0}^k\begin{Bmatrix}L\\i\end{Bmatrix}\dfrac{m!}{(m-i)!}\sum_{j=0}^{k-i}\binom{m-i}{j}\binom{n-m}{k-j-i}
\end{aligned}
我们已经地将右侧的和式转化为范德蒙德卷积的形式了。这样答案就可以表示为
\sum_{i=0}^{\min(k,L)}\begin{Bmatrix}L\\i\end{Bmatrix}\dfrac{m!}{(m-i)!}\binom{n-i}{k-i}
我们可以在 O(L\log L) 的时间内求出同一行的所有 第二类斯特林数，继而在 O(SL) 的时间内回答 S 组询问。不要忘记比上 \binom{n}{k}。
实现¶
#include <bits/stdc++.h>
typedef long long int ll;
const int maxn = 2e7 + 19, maxl = 2e5 + 19, mod = 998244353;
int qpow(int a, int b){
int res = 1;
while(b){
if(b & 1)
res = (ll)res * a % mod;
a = (ll)a * a % mod, b >>= 1;
}
return res;
}
int rev[maxl << 2], w[maxl << 2];
void dft(std::vector<int>::iterator f, int n, int b){
for(int i = 0; i < n; ++i)
if(i < rev[i])
std::swap(f[i], f[rev[i]]);
for(int i = 2; i <= n; i <<= 1){
w[0] = 1, w[1] = qpow(3, (mod - 1) / i); if(b == -1) w[1] = qpow(w[1], mod - 2);
for(int j = 2; j < i / 2; ++j) w[j] = (ll)w[j - 1] * w[1] % mod;
for(int j = 0; j < n; j += i){
std::vector<int>::iterator g = f + j, h = f + j + i / 2;
for(int k = 0; k < i / 2; ++k){
int p = g[k], q = (ll)h[k] * w[k] % mod;
g[k] = (p + q) % mod, h[k] = (p - q) % mod;
}
}
}
if(b == -1)
for(int i = 0, inv = qpow(n, mod - 2); i < n; ++i)
f[i] = (ll)f[i] * inv % mod;
}
std::vector<int> operator*(std::vector<int> F, std::vector<int> G){
int N = 1;
while(N < (int)(F.size() + G.size() - 1)) N <<= 1;
for(int i = 0; i < N; ++i) rev[i] = (rev[i >> 1] >> 1) | (i & 1 ? N >> 1 : 0);
F.resize(N), G.resize(N);
dft(F.begin(), N, 1), dft(G.begin(), N, 1);
for(int i = 0; i < N; ++i) F[i] = (ll)F[i] * G[i] % mod;
dft(F.begin(), N, -1);
F.resize(F.size() + G.size() - 1);
return F;
}
std::vector<int> F, G;
int N, M, S, L;
int fact[maxn], ifact[maxn];
inline int binom(int n, int m){
return (ll)fact[n] * ifact[n - m] % mod * ifact[m] % mod;
}
int main(){
std::scanf("%d%d%d%d", &N, &M, &S, &L);
if(N < L) N = L;
fact[0] = 1;
for(int i = 1; i <= N; ++i)
fact[i] = (ll)fact[i - 1] * i % mod;
ifact[N] = qpow(fact[N], mod - 2);
for(int i = N - 1; i >= 0; --i)
ifact[i] = (ll)ifact[i + 1] * (i + 1) % mod;
F.resize(L + 1), G.resize(L + 1);
for(int i = 0; i <= L; ++i)
F[i] = (i & 1 ? -1 : 1) * ifact[i], G[i] = (ll)qpow(i, L) * ifact[i] % mod;
F = F * G, F.resize(L + 1);
while(S--){
static int n, m, k, t, ans;
std::scanf("%d%d%d", &n, &m, &k), t = std::min({k, L, m, n}), ans = 0;
for(int i = 0; i <= t; ++i)
ans = (ans + (ll)F[i] * fact[m] % mod * ifact[m - i] % mod * binom(n - i, k - i)) % mod;
ans = (ll)ans * qpow(binom(n, k), mod - 2) % mod;
std::printf("%d\n", (ans + mod) % mod);
}
return 0;
}