20200727 T2 small w playing game [generating function (binomial inversion technique)]

Title Description

Topic analysis

Equipped with $i$ The number of schemes with odd number of times selected in the row is $f_i$,$j$ The number of schemes selected for odd number of times is $g_j$

$Ans={\sum }_{im+jn-2ij\le k}{f}_i\ast g_j$

$$f_i=q}^i(\frac{e^x+e^{-x}}{2}{)}^{n-i}\left(\genfrac{}{}{0ex}{}{n}{i}\right)$$

It's not easy to push directly （ But it is feasible , There's a little trick , I'll talk about it later ）

It would be more comfortable if there was only one power . Consider binomial inversion ,$h_i$ To force there to be $i$ Row odd , Any other scheme .

$$\begin{gathered} h_i=q}^i{e}^{(n-i)x}(\genfrac{}{}{0ex}{}{n}{i}) \\ =(\frac{1}{2}{)}^i\left(\genfrac{}{}{0ex}{}{n}{i}\right)q![x^q]\sum _{j=0}^i\left(\genfrac{}{}{0ex}{}{i}{j}\right)(-1{)}^{i-j}{e}^{x(n-2i+2j)} \end{gathered}$$
and $q![x^q]e^{x(n-2i+2j)}=(n-2i+2j{)}^q$

Then we can convolute .

Binomial inversion will be rolled up again .

We're done $f,g$ After enumeration $i$,$j(n-2i)\le k-im$, according to $n-2i$ You can find the corresponding prefix sum by the positive and negative of .

Note that rounding under negative division is larger .

Then I will talk about how to directly deduce the formula without binomial inversion .

For those two very similar bases , Express one in the form of another , namely ：
$$\begin{gathered} q![x^q]\left(\genfrac{}{}{0ex}{}{n}{i}\right)(\frac{1}{2}{)}^n(e^x-e^{-x}{)}^i(e^x+e^{-x}{)}^{n-i} \\ =q(\frac{1}{2}{)}^n(e^x+e^{-x}-2e^{-x}{)}^i(e^x+e^{-x}{)}^{n-i} \\ =q![x^q]\left(\genfrac{}{}{0ex}{}{n}{i}\right)(\frac{1}{2}{)}^n\sum _{j=0}^i(-2{)}^{i-j}(e^x+e^{-x}{)}^{n-i+j}{e}^{-x(i-j)} \\ =q(\frac{1}{2}{)}^n\sum _{j=0}^i(-2{)}^{i-j}\sum _{k=0}^{n-i+j}(\genfrac{}{}{0ex}{}{n-i+j}{k})e^{(2k-n)x} \\ =(\genfrac{}{}{0ex}{}{n}{i})(\frac{1}{2}{)}^n\sum _{j=0}^i(-2{)}^{i-j}\sum _{k=0}^{n-i+j}(\genfrac{}{}{0ex}{}{n-i+j}{k})(2k-n{)}^q \end{gathered}$$
the second $\sum$ Can be seen as $G(i-j)$, One convolution can find $G$, Then we can roll it again and find out $f$ 了 .

Code（ Binomial inversion ）：

#include<bits/stdc++.h>
#define maxn 550005
using namespace std;
const int mod = 998244353, inv2 = (mod+1)/2;
int w[maxn],r[maxn],WL,fac[maxn],inv[maxn];
int Pow(int a,int b){
    int s=1;for(;b;b>>=1,a=1ll*a*a%mod) b&1&&(s=1ll*s*a%mod);return s;}
int C(int n,int m){
    return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;}
void init(int n){
    
	w[0]=WL=1; while(WL<=n) WL<<=1; w[1]=Pow(3,(mod-1)/WL);
	for(int i=2;i<=WL;i++) w[i]=1ll*w[i-1]*w[1]%mod;
	fac[0]=fac[1]=inv[0]=inv[1]=1;
	for(int i=2;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod,inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	for(int i=2;i<=n;i++) inv[i]=1ll*inv[i-1]*inv[i]%mod;
}
int upd(int x){
    return x+(x>>31&mod);}
void NTT(int *a,int len,int flg){
    
	for(int i=0;i<len;i++) if(i<(r[i]=r[i>>1]>>1|(i&1?len>>1:0))) swap(a[i],a[r[i]]);
	for(int i=2,l=1,v;i<=len;l=i,i<<=1)
		for(int j=0,t=WL/i;j<len;j+=i)
			for(int k=j,o=0;k<j+l;k++,o+=t)
				a[k+l]=upd(a[k]-(v=1ll*w[flg^1?WL-o:o]*a[k+l]%mod)),a[k]=upd(a[k]+v-mod);
	if(flg^1) for(int i=0,Inv=mod-(mod-1)/len;i<len;i++) a[i]=1ll*a[i]*Inv%mod;
}
int n,m,qq,A[maxn],B[maxn],f[maxn],g[maxn],h[maxn];
long long q,k,lim;
void calc(int n,int *f){
    
	init(2*n);
	memset(A,0,sizeof A),memset(B,0,sizeof B);
	for(int i=0;i<=n;i++) A[i]=inv[i],B[i]=1ll*(i&1?mod-1:1)*inv[i]%mod*Pow(upd(n-2*i),qq)%mod;
	NTT(A,WL,1),NTT(B,WL,1);
	for(int i=0;i<WL;i++) A[i]=1ll*A[i]*B[i]%mod;
	NTT(A,WL,-1); memset(h,0,sizeof h);
	for(int i=0,pw=1;i<=n;i++,pw=1ll*pw*inv[2]%mod) h[i]=1ll*A[i]*fac[n]%mod*inv[n-i]%mod*pw%mod;
	memset(A,0,sizeof A),memset(B,0,sizeof B);
	for(int i=0;i<=n;i++) A[i]=1ll*h[i]*fac[i]%mod,B[i]=1ll*inv[n-i]*(n-i&1?mod-1:1)%mod;
	NTT(A,WL,1),NTT(B,WL,1);
	for(int i=0;i<WL;i++) A[i]=1ll*A[i]*B[i]%mod;
	NTT(A,WL,-1);
	for(int i=0;i<=n;i++) f[i]=1ll*A[n+i]*inv[i]%mod;
}
int main()
{
    
	freopen("b.in","r",stdin);
	freopen("b.out","w",stdout);
	scanf("%d%d%lld%lld",&n,&m,&q,&k),qq=q%(mod-1);
	if(q==0) return puts("1"),0;
	calc(n,f),calc(m,g);
	for(int i=1;i<=m;i++) g[i]=(g[i]+g[i-1])%mod;
	int ans=0;
	for(int i=0;i<=n;i++)
		if(n>2*i){
    
			if(k>=1ll*i*m) ans=(ans+1ll*f[i]*g[min((k-1ll*i*m)/(n-2*i),1ll*m)])%mod;
		}
		else if(n<2*i){
    
			if((lim=(1ll*i*m-k+2*i-n-1)/(2*i-n))<=m) ans=(ans+1ll*f[i]*(g[m]-(lim>0?g[lim-1]:0)))%mod;
		}
		else if(k-1ll*i*m>=0) ans=(ans+1ll*f[i]*g[m])%mod;
	printf("%d\n",(ans+mod)%mod);
}