Submission #31265087

---

Source Code Expand

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

#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define per(i,l,r) for(int i=(l);i>=(r);i--)

const int N=250005;
const int mod=998244353;

inline int qpow(int a,int b=mod-2){
	int res=1;
	while(b>0){
		if(b&1)res=1ll*res*a%mod;
		a=1ll*a*a%mod,b>>=1;
	}
	return res;
}

const int inv2=qpow(2);
const int inv4=qpow(4);

int f[N],g[N],h[N];
int n,m;

int two[N];
int pw[N],ipw[N],fac[N],ifac[N];
void init(int n){
	two[0]=1;rep(i,1,n)two[i]=2*two[i-1]%mod;
	rep(i,0,n)pw[i]=(mod+1-two[i])%mod;
	rep(i,0,n)ipw[i]=qpow(pw[i]);
	fac[0]=1;rep(i,1,n)fac[i]=1ll*fac[i-1]*pw[i]%mod;
	ifac[n]=qpow(fac[n]);per(i,n,1)ifac[i-1]=1ll*ifac[i]*pw[i]%mod;
}
inline int C(int n,int m){
	return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
inline int sqr(int x){return 1ll*x*x%mod;}

int main(){
	cin>>n>>m,init(N-1);
	g[0]=1;
	rep(i,1,m)g[i]=1ll*g[i-1]*(two[i-1]-two[m]+mod)%mod*ipw[i]%mod;
	// rep(i,0,m)printf("g[%d]=%d\n",i,g[i]);
	rep(i,0,m-1)f[0]=(f[0]+sqr(two[i]))%mod;
	rep(i,1,min(n,m)){
		int coef=(1ll*two[i+1]*f[i-1]%mod+mod-1ll*sqr(two[m])*g[i]%mod)%mod;
		f[i]=1ll*coef*ipw[i+2]%mod;
	}
	// rep(i,0,m)printf("f[%d]=%d\n",i,f[i]);
	h[0]=1;
	rep(i,1,min(n,m)){
		h[i]=1ll*h[i-1]*(mod+1-two[n-i+1])%mod*ipw[i]%mod;
		// printf("h[%d]=%d\n",i,h[i]);
	}
	int ans=0,tot=two[m],FAC=1;
	rep(i,1,min(n,m)){
		FAC=1ll*FAC*i%mod;
		int coef=0;
		coef=(coef+2ll*f[i-1])%mod;
		coef=(coef+mod-g[i])%mod;
		coef=(coef+1ll*(tot-1)*g[i]%mod+mod-1ll*(i+1)*g[i+1]%mod)%mod;
		// int ex=(1ll*(i-1)*i/2+1)%(mod-1);
		// ans=(ans+1ll*h[i]*coef%mod*FAC%mod*qpow(inv2,ex))%mod;
		ans=(ans+1ll*h[i]*coef%mod*inv2%mod*fac[i]%mod*(i&1?mod-1:1))%mod;
		// printf("coef=%d\n",1ll*h[i]*coef%mod*qpow(inv2,ex)%mod);
		// printf("ans=%d\n",ans);
	}
	cout<<ans<<'\n';
	return 0;
}

Submission Info

Judge Result