传送门

把有气和没气看反结果推了一下午，果然是我对cxk的爱还不够深沉吗

枚举投中了球，易知答案为$\dfrac{\sum\limits_{i=0}^kC_m^iC_{n-m}^{k-i}i^L}{C_n^k}$

大力搞分子。考虑到$L$相对较小，用第二类斯特林数展开$L$次方：

$\sum\limits_{j=0}^L\begin{Bmatrix}L\\j\end{Bmatrix}j!\sum\limits_{i=0}^kC_i^jC_m^iC_{n-m}^{k-i}$

这里出现了一个经典的等式：$C_i^jC_m^i=C_m^jC_{m-j}^{i-j}$：

$=\sum\limits_{j=0}^L\begin{Bmatrix}L\\j\end{Bmatrix}C_m^jj!\sum\limits_{i=0}^kC_{m-j}^{i-j}C_{n-m}^{k-i}$

感觉后面长得很范德蒙，又由于$i\in[0,j-1]$的时候$C_{m-j}^{i-j}$都没有意义，统一把$i$换成$i+j$：

$=\sum\limits_{j=0}^L\begin{Bmatrix}L\\j\end{Bmatrix}C_m^jj!\sum\limits_{i=0}^{k-j}C_{m-j}^iC_{n-m}^{k-j-i}$

大名鼎鼎的范德蒙恒等式就出来了：$\sum\limits_{i=0}^{k-j}C_{m-j}^iC_{n-m}^{k-j-i}=C_{n-j}^{k-j}$。

于是答案就是$\dfrac{\sum\limits_{j=0}^L\begin{Bmatrix}L\\j\end{Bmatrix}C_m^jC_{n-j}^{k-j}j!}{C_n^k}$。

$NTT$预处理一行第二类斯特林数，每次询问暴力$O(L)$回答，复杂度$O(N+L\log L+SL)$。

听说有点卡常，把组合数拆开约分一下就好了。不知道为啥吸氧比不吸氧慢了一倍。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define maxn 20000005    
#define inf 0x3f3f3f3f

const int mod = 998244353;
const int g = 3;

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
inline int quickpow(int x,int y=mod-2){
    int ans=1;
    while(y){
        if(y&1)ans=1ll*ans*x%mod;
        x=1ll*x*x%mod,y>>=1;
    }
    return ans;
}
const int ig = quickpow(g);
int tr[1000005];
inline int qm(int x){return x>=mod?x-mod:x;}
void NTT(int *f,int n,bool t){
    for(register int i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
    for(register int p=2;p<=n;p<<=1){
        int len=p>>1,o=quickpow(t?ig:g,(mod-1)/p);
        for(register int i=0;i<n;i+=p){
            int gen=1,cop;
            for(register int j=i;j<i+len;++j){
                cop=1ll*f[j+len]*gen%mod,gen=1ll*gen*o%mod;
                f[j+len]=qm(f[j]+mod-cop),f[j]=qm(f[j]+cop);
            }
        }
    }
    if(t){
        int inv=quickpow(n);
        for(register int i=0;i<n;++i)f[i]=1ll*f[i]*inv%mod;
    }
}
int fac[maxn]={1},inv[maxn]={1},F[1000005],G[1000005];
int main(){
    int n=read(),m=read(),s=read(),l=read(),k=max(max(n,m),l);
    for(register int i=1;i<=k;++i)fac[i]=1ll*fac[i-1]*i%mod;
    inv[k]=quickpow(fac[k]);
    for(register int i=k-1;~i;--i)inv[i]=1ll*inv[i+1]*(i+1)%mod;
    for(register int i=0;i<=l;++i)F[i]=i&1?mod-inv[i]:inv[i],G[i]=1ll*quickpow(i,l)*inv[i]%mod;
    k=1;
    while(k<=l<<1)k<<=1;
    for(register int i=0;i<k;++i)tr[i]=(tr[i>>1]>>1)|(i&1?k>>1:0);
    NTT(F,k,0),NTT(G,k,0);
    for(register int i=0;i<k;++i)F[i]=1ll*F[i]*G[i]%mod;
    NTT(F,k,1);
    while(s--){
        int ans=0;
        n=read(),m=read(),k=read();
        for(register int i=min(min(m,k),l);~i;--i)ans=qm(ans+1ll*F[i]*fac[n-i]%mod*inv[m-i]%mod*inv[k-i]%mod);
        printf("%d\n",1ll*ans*fac[k]%mod*fac[m]%mod*inv[n]%mod);
    }
}