你猜猜题怎么出出来的？

显然第\(i\)场的答案为

\[ \frac{1}{\binom{n_i}{m_i}\binom{n_i}{k_i}}\sum_{x=0}^{k_i}\binom{n_i}{m_i}\binom{m_i}{x}\binom{n_i-m_i}{k_i-x}x^L =\frac{1}{\binom{n_i}{k_i}}\sum_{x=0}^{k_i}\binom{m_i}{x}\binom{n_i-m_i}{k_i-x}x^L\\ \]

利用斯特林数进行变换

\[ \sum_{x=0}^{k_i}\binom{m_i}{x}\binom{n_i-m_i}{k_i-x}x^L =\sum_{x=0}^{k_i}\binom{m_i}{x}\binom{n_i-m_i}{k_i-x}\sum_{y=0}^{x}y!\binom{x}{y}\left\{\begin{matrix}L\\y\end{matrix}\right\}\\ =\sum_{y=0}^{k_i}y!\left\{\begin{matrix}L\\y\end{matrix}\right\} \sum_{x=y}^{k_i}\binom{x}{y}\binom{m_i}{x}\binom{n_i-m_i}{k_i-x}\\ =\sum_{y=0}^{k_i}y!\left\{\begin{matrix}L\\y\end{matrix}\right\} \sum_{x=y}^{k_i}\binom{m_i}{y}\binom{m_i-y}{x-y}\binom{n_i-m_i}{k_i-x}\\ =\sum_{y=0}^{k_i}y!\binom{m_i}{y}\left\{\begin{matrix}L\\y\end{matrix}\right\} \sum_{x=0}^{k_i-y}\binom{m_i-y}{x}\binom{n_i-m_i}{k_i-y-x}\\ =\sum_{y=0}^{k_i}y!\binom{m_i}{y}\left\{\begin{matrix}L\\y\end{matrix}\right\} \binom{n_i-y}{k_i-y} \]

发现\(y\)的实际上界为\(\min(k_i,m_i,L)\)不过\(1e5\)，而询问仅\(2e2\)，预处理第\(L\)行斯特林数，询问复杂度\(O(L)\)可以接受。

斯特林数的预处理。

最终答案为

\[ \sum_{i=1}^S\frac{k_i!(n_i-k_i)!}{n_i!}\sum_{y=0}^{k_i}y!\frac{m_i!(n_i-y)!}{y!(m_i-y)!(k_i-y)!(n_i-k_i)!}S(L,y)\\ =\sum_{i=1}^S\frac{k_i!m_i!}{n_i!}\sum_{y=0}^{k_i}\frac{(n_i-y)!}{(m_i-y)!(k_i-y)!}S(L,y) \]

显得十分的和谐。

此题卡常

#include 
    
     #define IL inline #define ll long long using namespace std;const int N=8e5+10;const int M=2e7+10;const int mod=998244353;IL ll gi(){    ll x=0,f=1;    char ch=getchar();    while(!isdigit(ch))f^=ch=='-',ch=getchar();    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();    return f?x:-x;}int lmt,w[N],rev[N];IL int fpw(int x,int y) {    int c=1;    for(; y; y>>=1,x=(ll)x*x%mod) if(y&1) c=(ll)c*x%mod;    return c;}IL void init(int n) {    int l=0; lmt=1;    while(lmt<=n) lmt<<=1, l++;     for(int i=0; i
     
      >1]>>1)|((i&1)<<(l-1));    int tmp=lmt>>1, wlmt=fpw(3,(mod-1)>>l); w[tmp]=1;    for(int i=tmp+1; i
      
       >u]=a[i];    for(int m=1; m