Note: the variable names used in the problem solution are different from those in the problem
Given the coefficient ， kk, multiple groups of query hypergeometric distribution ， xx~H(n,M,N)H(n,M,N) to the ， kk ， power ， E(x^k)E(xk).
Difficulty positioning: simple purple question, culture class contestants should be able to solve it in seconds.
The first two grades are respectively a set of textbook expected variance formula and a direct enumeration of several shots, which are calculated by hypergeometric distribution formula.
iN hypergeometric distribution, P (x = I) = \ frac {\ tbinom {M} {I} \ tbinom {n-i} {\ tbinom {n}} P (x = I) = (NN) (iM) (n − iN − M)
therefore
ans=\sum_{i=0}^ni^k*\frac{\tbinom{M}{i}\tbinom{N-M}{n-i}}{\tbinom{N}{n}}=\sum_{i=1}^ni^k*\frac{\tbinom{M}{i}\tbinom{N-M}{n-i}}{\tbinom{N}{n}}ans=i=0∑nik∗(nN)(iM)(n−iN−M)=i=1∑nik∗(nN)(iM)(n−iN−M)
Considering that the combination meaning of ， i^kik ， is the number of schemes to put ， kk different balls into ， ii different boxes, let ， S_2(k,j)S2 (k,j) (the second kind of Stirling number) represents the number of schemes that put # kk # different balls into # jj # the same box and require the box to be non empty. Considering enumerating the number of non empty boxes # jj # then it is obvious that
i^k=\sum_{j=0}^iS_2(k,j)j!\tbinom{i}{j}ik=j=0∑iS2(k,j)j!(ji)
Substituting the formula in the question can get
\sum_{i=1}^ni^k\frac{\tbinom{M}{i}\tbinom{N-M}{n-i}}{\tbinom{N}{n}}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \i=1∑nik(nN)(iM)(n−iN−M)
=\frac{\sum_{i=1}^n\tbinom{M}{i}\tbinom{N-M}{n-i}\sum_{j=0}^kS_2(k,j)j!\tbinom{i}{j}}{{\tbinom{N}{n}}}=(nN)∑i=1n(iM)(n−iN−M)∑j=0kS2(k,j)j!(ji)
Exchange summation order
=\frac{\sum_{j=0}^kS_2(k,j)j!\sum_{i=1}^n\tbinom{M}{i}\tbinom{i}{j}\tbinom{N-M}{n-i}}{{\tbinom{N}{n}}}=(nN)∑j=0kS2(k,j)j!∑i=1n(iM)(ji)(n−iN−M)
Considering the combined meaning of \ tbinom{M}{i}\tbinom{i}{j}(iM) (ji), it is to select {ii} individuals from {MM} individuals to participate in the competition, and then select} jj} winners from {ii} individuals.
Then we can choose − jj − individual award first, and then choose − i-ji − j − individual award − 00
You can get \ tbinom{M}{i}\tbinom{i}{j}=\tbinom{M}{j}\tbinom{M-j}{i-j}(iM) (ji) = (jM) (i − jM − j)
Therefore, the original formula is changed into the following formula (independent of ， ii ， throw in front)
\ \ \ \ \ \ \ =\frac{\sum_{j=0}^kS_2(k,j)j!\tbinom{M}{j}\sum_{i=1}^n\tbinom{M-j}{i-j}\tbinom{N-M}{n-i}}{{\tbinom{N}{n}}} =(nN)∑j=0kS2(k,j)j!(jM)∑i=1n(i−jM−j)(n−iN−M)
The latter thing is a van der Monde convolution, which is further simplified
=\frac{\sum_{j=0}^kS_2(k,j)j!\tbinom{M}{j}\tbinom{N-j}{n-j}}{{\tbinom{N}{n}}}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \=(nN)∑j=0kS2(k,j)j!(jM)(n−jN−j)
So as long as you know ， S_2(k,j)S2 (k,j) can calculate the answer of O(k)O(k), and the complexity of O(qk)O(qk) can pass this question.
Consider the second kind of Stirling number s_ The combinatorial meaning of 2 (k,j) S2 (k,j) can be obtained by using the principle of tolerance and exclusion
S_2(k,j)=\frac{1}{j!}\sum_{i=0}^j(-1)^i(j-i)^k\tbinom{j}{i}=\sum_{i=0}^j\frac{(-1)^i(j-i)^k}{i!(j-i)!}S2(k,j)=j!1i=0∑j(−1)i(j−i)k(ij)=i=0∑ji!(j−i)!(−1)i(j−i)k
Let generating function f(x)=\sum_i(-1)^ii!*x^i,g(x)=\sum_i\frac{i^k}{i!}*x^if(x)=∑i(−1)ii! ∗xi,g(x)=∑ii!ik * Xi, obviously for a given K K, S_2(k,j)S2 (k,j) is the coefficient of x^jxj in f*gf * g ， so ， f(x),g(x)f(x),g(x) (i^kik can be treated with linear sieve), and then {NTT} NTT ， o (klog_2k+N) O (Klog 2 ， k+N) can calculate the required second kind of Stirling number, so as to calculate the result. Total complexity O(N+k(q+log_2k))O(N+k(q+log2_2k)).
code
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=5.5e5,M=2e7+2,p=998244353;
int f[N],g[N],r[N],yg[N],ig[N],ifac[M],fac[M],ss[N],mc[N];
int c;
inline int ksm(register int x,register int y)
{
register int r=1;
while (y)
{
if (y&1) r=(ll)r*x%p;
x=(ll)x*x%p;
y>>=1;
}
return r;
}
void dft(register int *a,register int xs,register int limit)
{
register int i,j,k,l,w,wn,b,c;
for (i=1;i<limit;i++) if (i<r[i]) swap(a[i],a[r[i]]);
for (i=1;i<limit;i=l)
{
l=i<<1;
if (xs) wn=ig[l]; else wn=yg[l];
for (j=0;j<limit;j+=l)
{
w=1;
for (k=0;k<i;k++,w=(ll)w*wn%p)
{
b=a[j|k];c=(ll)w*a[j|k|i]%p;
a[j|k]=(b+c)%p;
a[j|k|i]=(b-c+p)%p;
}
}
}
if (xs)
{
limit=ksm(limit,p-2);
for (i=0;i<xs;i++) a[i]=(ll)a[i]*limit%p;
}
}
inline void read(int &x)
{
c=getchar();
while ((c<48)||(c>57)) c=getchar();
x=c^48;c=getchar();
while ((c>=48)&&(c<=57))
{
x=x*10+(c^48);
c=getchar();
}
}
int main()
{
register int n,m,q,k,i,j,x,limit=1,l=0,gs=0;
read(n);read(c);read(q);read(k);
while (limit<=k) limit<<=1,++l;
n=max(n,limit-1);
limit<<=1;
for (i=1;i<limit;i++) r[i]=r[i>>1]>>1|(i&1)<<l;
ig[limit]=ksm(yg[limit]=ksm(3,(p-1)/limit),p-2);
for (i=limit>>1;i;i>>=1)
{
yg[i]=(ll)yg[i<<1]*yg[i<<1]%p;
ig[i]=(ll)ig[i<<1]*ig[i<<1]%p;
}
l=limit>>1;ifac[0]=ifac[1]=fac[0]=fac[1]=1;
for (i=2;i<=n;i++) ifac[i]=p-(ll)p/i*ifac[p%i]%p,fac[i]=(ll)fac[i-1]*i%p;
for (i=2;i<=n;i++) ifac[i]=(ll)ifac[i-1]*ifac[i]%p;
mc[1]=1;
for (i=2;i<l;i++)
{
if (!mc[i]) mc[ss[++gs]=i]=ksm(i,k);
for (j=1;(j<=gs)&&(i*ss[j]<l);j++)
{
mc[i*ss[j]]=(ll)mc[i]*mc[ss[j]]%p;
if (i%ss[j]==0) break;
}
}
for (i=0;i<l;i++) if (i&1) f[i]=p-ifac[i]; else f[i]=ifac[i];
for (i=1;i<l;i++) g[i]=(ll)ifac[i]*mc[i]%p;
dft(f,0,limit);dft(g,0,limit);
for (i=0;i<limit;i++) f[i]=(ll)f[i]*g[i]%p;
dft(f,l,limit);
while (q--)
{
read(n);read(m);read(x);
j=0;
for (i=min(min(x,m),k);i;i--) j=(j+(ll)f[i]*ifac[m-i]%p*fac[n-i]%p*ifac[x-i])%p;
printf("%d\n",int((ll)j*ifac[n]%p*fac[x]%p*fac[m]%p));
}
}
update: due to the shortened time limit, this code has been unable to pass this question. Please use efficient factorial / factorial inverse preprocessing.