Submission #43411939

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const ll MAXN=(1<<22),mod=998244353;

void add(ll& x,ll y){x=(x+y)%mod;}
void sub(ll& x,ll y){x=(x-y+mod)%mod;}
ll addv(ll x,ll y){return (x+y)%mod;}
ll subv(ll x,ll y){return (x-y+mod)%mod;}

void tomax(ll& x,ll y){x=max(x,y);}
void tomin(ll& x,ll y){x=min(x,y);}

ll mypow(ll a,ll n){
	ll ret = 1,pw = a;
	while(n){
		if(n&1)ret = ret * pw%mod;
		pw = pw*pw%mod;
		n>>=1;
	}
	return ret;
}
ll myinv(ll a){
	return mypow(a,mod-2);
}

const ll div3 = myinv(3);

typedef vector<ll> Poly;

int SZ(const Poly& v){return v.size();}

void up(Poly& v,int n){
	if(SZ(v) < n)v.resize(n,0);
}
void cut(Poly& v,int n){
	if(SZ(v) > n)v.resize(n,0);
}
void reset(Poly& v,int n){
	up(v,n);
	cut(v,n);
}

Poly operator+(const Poly& x,const Poly& y){
	Poly z(max(SZ(x),SZ(y)),0);
	rep(i,0,SZ(z)-1){
		z[i] = addv((i<SZ(x)) ? (x[i]) : (0),(i<SZ(y)) ? (y[i]) : 0);
	}
	return z;
}
Poly operator-(const Poly& x,const Poly& y){
	Poly z(max(SZ(x),SZ(y)),0);
	rep(i,0,SZ(z)-1){
		z[i] = subv((i<SZ(x)) ? (x[i]) : (0),(i<SZ(y)) ? (y[i]) : 0);
	}
	return z;
}

namespace _{
	ll f[MAXN],g[MAXN],h[MAXN],W[MAXN];
	int rev[MAXN],N;

	void transform(ll* f){rep(i,0,N-1)if(i<rev[i])swap(f[i],f[rev[i]]);}
	void DFT(ll* f,ll a){
		transform(f);
		ll pw = mypow(a,(mod-1)/N);
		W[0]=1;rep(i,1,N-1)W[i] = W[i-1]*pw%mod;

		for(int len=2;len<=N;len<<=1)for(int i=0;i<N;i+=len)rep(j,0,len/2-1){
			ll w = W[j*(N/len)];
			ll x = f[i+j],y = f[i+j+len/2];
			f[i+j] = addv(x,w*y);
			f[i+j+len/2] = subv(x,w*y%mod);
		}
	}
	void FFT(const Poly& x,const Poly& y,Poly& z){
		int n = SZ(x)-1,m = SZ(y)-1;
		N=1;while(N<=n+m)N<<=1;

		rep(i,0,N-1){
			f[i] = g[i] = h[i] = 0;
			rev[i] = rev[i>>1] >> 1;
			if(i&1)rev[i] |= (N>>1);
		}
		rep(i,0,n)f[i] = x[i];
		rep(i,0,m)g[i] = y[i];
		DFT(f,3);DFT(g,3);
		rep(i,0,N-1)h[i] = f[i]*g[i]%mod;
		DFT(h,div3);
		reset(z,n+m+1);
		ll inv = myinv(N);
		rep(i,0,n+m)z[i] = h[i]*inv%mod;
	}
};

Poly operator*(const Poly& x,const Poly& y){
	Poly z;
	_::FFT(x,y,z);
	return z;
}

//
namespace CFM{
	const int MAXM = 2e5+10;

	int n,m,p,q,ca[MAXN],cb[MAXN],M;

	Poly calc(const Poly& A){
		Poly ret(M);
		int sz = A.size();
		rep(i,0,sz-1)add(ret[i%M],A[i]);
		return ret;
	}

	Poly mypow(const Poly& A,int n){
		if(!n){
			Poly I(M);
			I[0] = 1;
			return I;
		}
		Poly B = mypow(A,n/2);
		B = B*B;
		if(n&1)B = B*A;

		return calc(B);
	}
	
	void solve(){
		cin>>n>>m>>p>>q;
		rep(i,1,p){
			int num;cin>>num;
			ca[num]++;
		}
		rep(i,1,q){
			int num;cin>>num;
			cb[num]++;
		}
		//
		M = 2*m+2; //mod x^M -1
		
		Poly F(M);
		rep(i,1,m){
			F[i] = ca[i];
			F[M-i] = (mod-ca[i])%mod;
		}

		Poly X(M);
		X[0] = X[1] = X[M-1] = 1;
		//计算 F * X^(n-1)

		F = F * mypow(X,n-1);

		F = calc(F);

		ll ans = 0;

		rep(i,1,m){
			add(ans,F[i] * cb[i]%mod);
		}

		cout<<ans<<endl;
	}	
};

int main(){
	CFM::solve();

    return 0;
}

Submission Info

Judge Result