幼儿园篮球题

---

传送门

---

思路

不难发现，我们要求的答案实际上是这个东西:

$$\frac{\sum_{i=0}^{k} i^{L}\left(\begin{array}{c} m \\ i \end{array}\right)\left(\begin{array}{c} n-m \\ k-i \end{array}\right)}{\left(\begin{array}{l} n \\ k \end{array}\right)}$$

于是，我们只需求到分子即可。我们开始愉快的化式子了。

$$\sum_{i=0}^{k} i^{L}\left(\begin{array}{c} m \\ i \end{array}\right)\left(\begin{array}{c} n-m \\ k-i \end{array}\right)$$

我们发现里面难搞的其实是 $i^{L}$ ，但是我们又有式子:

$$n^{m}=\sum_{i=0}^{n}\left(\begin{array}{c} n \\ i \end{array}\right) i !\left\{\begin{array}{c} m \\ i \end{array}\right\}$$

对于这个式子的感性证明就是：假设我们现在有 $m$ 个小球，要放进 $n$ 个盒子里面，没有限制，显然它等于 $n^{m}$ 。但是，我们还有一种求法，即，我们选出 $i$ 个盒子放 $m$ 个小球，显然要选出 $i$ 个盒子，然后把 $m$ 个小球塞进去，又因为盒子不同，所以还要乘上 $i$ 。

将上式代入式子中，可以得到:

$$=\sum_{i=0}^{k}\left(\begin{array}{c} m \\ i \end{array}\right)\left(\begin{array}{c} n-m \\ k-i \end{array}\right) \sum_{j=0}^{i}\left(\begin{array}{l} i \\ j \end{array}\right) j !\left\{\begin{array}{l} L \\ j \end{array}\right\}$$

又因为

$$\left(\begin{array}{c} m \\ i \end{array}\right)\left(\begin{array}{l} i \\ j \end{array}\right)=\left(\begin{array}{c} m \\ j \end{array}\right)\left(\begin{array}{c} m-j \\ i-j \end{array}\right)$$

这个式子展开之后易证。
所以原式等于:

$$\begin{array}{l} =\sum_{j=0}^{k}\left\{\begin{array}{l} L \\ j \end{array}\right\} j !\left(\begin{array}{c} m \\ j \end{array}\right) \sum_{i=j}^{k}\left(\begin{array}{c} m-j \\ i-j \end{array}\right)\left(\begin{array}{c} n-m \\ k-i \end{array}\right) \\ =\sum_{j=0}^{k}\left\{\begin{array}{l} L \\ j \end{array}\right\} j !\left(\begin{array}{c} m \\ j \end{array}\right) \sum_{i=0}^{k-j}\left(\begin{array}{c} m-j \\ i \end{array}\right)\left(\begin{array}{c} n-m \\ k-i-j \end{array}\right) \end{array}$$

然后你发现后面那个式子是范德蒙德卷积，就等于:

$$\left(\begin{array}{l} n-j \\ k-j \end{array}\right)$$

所以原式等于:

$$=\sum_{j=0}^{k}\left\{\begin{array}{c} L \\ j \end{array}\right\} j !\left(\begin{array}{c} m \\ j \end{array}\right)\left(\begin{array}{l} n-j \\ k-j \end{array}\right)$$

又因为上面提到的 $n^{m}=\sum_{i=0}^{n}\left(\begin{array}{c}n \\ i\end{array}\right) i !\left\{\begin{array}{c}m \\ i\end{array}\right\}$, 这个东西我们可以使用二项式反演得到:

$$\left\{\begin{array}{l} m \\ n \end{array}\right\}=\sum_{i=0}^{n} \frac{i^{m}}{i !} \frac{(-1)^{n-i}}{(n-i) !}$$

然后你就发现这是个卷积形式，于是我们就可以 $\Theta(L \log L)$ 预处理出 $\left\{\begin{array}{l}L \\ j\end{array}\right\}$ 。
不过因为这道题十分卡常，所以我们还需要再化一下式子。

$$\begin{array}{c} \text { ans }=\frac{\sum_{j=0}^{k}\left\{\begin{array}{l} L \\ j \end{array}\right\} j !\left(\begin{array}{c} m \\ j \end{array}\right)\left(\begin{array}{c} n-j \\ k-j \end{array}\right)}{\left(\begin{array}{l} n \\ k \end{array}\right)} \\ =\left(\sum_{j=0}^{k}\left\{\begin{array}{l} L \\ j \end{array}\right\} j ! \frac{m !}{j !(m-j) !} \frac{(n-j) !}{(k-j) !(n-k) !}\right) \frac{k !(n-k) !}{n !} \\ =\left(\sum_{j=0}^{k}\left\{\begin{array}{l} L \\ j \end{array}\right\} \frac{(n-j) !}{(m-j) !(k-j) !}\right) \frac{k ! m !}{n !} \end{array}$$

我们又发现上界其实是 $\min \{n, k, L\}$ ，所以至此，我们可以 $\Theta(L \log L+S L)$ 解决此题目。

---

$Code$

#include <bits/stdc++.h>
using namespace std;

#define Int register int
#define MAXX 20000005
#define mod 998244353
#define Gi 332748118
#define MAXN 800005
#define G 3 

int quick_pow (int a,int b,int c){
	int res = 1;
	while (b){
		if (b & 1) res = 1ll * res * a % c;
		a = 1ll * a * a % c;
		b >>= 1;
	}
	return res;
}

int l,limit,r[MAXN];

void NTT (int *a,int type){
	for (Int i = 0;i < limit;++ i)
		if (i < r[i]) swap (a[i],a[r[i]]);
	for (Int mid = 1;mid < limit;mid <<= 1){
		int Wn = quick_pow (type == 1 ? G : Gi,(mod - 1) / (mid << 1),mod);
		for (Int R = mid << 1,j = 0;j < limit;j += R){
			int w = 1;
			for (Int k = 0;k < mid;++ k,w = 1ll * w * Wn % mod){
				int x = a[j + k],y = 1ll * w * a[j + k + mid] % mod;
				a[j + k] = (x + y) % mod,a[j + k + mid] = (x + mod - y) % mod;
			} 
		} 
	}
	if (type == 1) return ; 
	int Inv = quick_pow (limit,mod - 2,mod);
	for (Int i = 0;i < limit;++ i) a[i] = 1ll * a[i] * Inv % mod;
}

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}

int N,M,S,L;
int A[MAXN],B[MAXN];

int inv[MAXX],fac[MAXX];

void SiteLin (int n){
	for (Int i = 0;i <= n;++ i){
		A[i] = (i & 1) ? mod - inv[i] : inv[i];
		B[i] = 1ll * quick_pow (i,n,mod) * inv[i] % mod;
	}
	limit = 1,l = 0;
	while (limit <= (n << 1)) limit <<= 1,l ++;
	for (Int i = 0;i < limit;++ i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << l - 1);
	NTT (A,1),NTT (B,1);
	for (Int i = 0;i < limit;++ i) A[i] = 1ll * A[i] * B[i] % mod;
	NTT (A,-1);
}

int C (int n,int m){
	return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
}

signed main(){
	read (N,M,S,L);
	inv[0] = inv[1] = fac[0] = 1;int uu = max (N,L);
	for (Int i = 1;i <= uu;++ i) fac[i] = 1ll * fac[i - 1] * i % mod;
	inv[uu] = quick_pow (fac[uu],mod - 2,mod);
	for (Int i = uu - 1;~i;-- i) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
	SiteLin (L);
	while (S --){
		int n,m,k;
		read (n,m,k);int ans = 0;
		for (Int i = 0;i <= min (L,min (m,k));++ i) ans = (ans + 1ll * A[i] * inv[m - i] % mod * fac[n - i] % mod * inv[k - i]) % mod;
		write (1ll * ans * fac[m] % mod * fac[k] % mod * inv[n] % mod),putchar ('\n');
	}
	return 0;
}