yukicoder : No.3486 Draw a Rainbow

問題

２つの国があり、虹を前者はM色、後者はL色で塗る習慣がある。
ここでN個のペンがある。
各ペンは、前者の国ではA[i]番目の色、後者の国ではB[i]番目の色として見られる色をしている。
ペンの部分集合(2^N-1)通りのうち、前者の国でもM色全部、後者の国でもL色全部をカバーするようなものは何通りか。

解法

高速ゼータ変換と、畳み込みで解く。

F(i,mask) := 前者の国でi番の色で見えるペンの空でない部分集合のうち、後者の色では総じてmaskで示すbitmaskに相当する色をカバーする選びかたの数
上記は高速ゼータ変換で求められる。
あとはF(0,mask(0)) * F(1,mask(1)) .... * F(M-1,mask(M-1))のうち、mask(0) or mask(1) or ... mask(M-1)がL色全部をカバーするようなケースの総和を求めればよい。

bitwise-or convolutionは以下のページなどで計算方法が書かれている。(bitwise-orについては最後のchemthan氏のコメント参照)
Fast Fourier Transform and variations of it

int N,M,L;
int V[18][18];

ll p2[202020];

const ll mo=998244353;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

vector<ll> fft_or(vector<ll> v, bool rev=false) {
	int n=v.size(),i,j,m;
	
	for(int m=2; m<=n; m*=2) {
		for(i=0;i<n;i+=m) {
			for(int j1=i,j2=i+m/2;j2<i+m;j1++,j2++) {
				ll t1=v[j1],t2=v[j2];
				
				if(!rev) {
					v[j2]=(t1+t2)%mo;
				}
				else {
					v[j2]=(t2-t1+mo)%mo;
				}
				
			}
		}
	}
	return v;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p2[0]=1;
	FOR(i,202010) p2[i+1]=p2[i]*2%mo;
	
	
	cin>>N>>M>>L;
	FOR(i,N) {
		cin>>x>>y;
		V[x-1][y-1-M]++;
	}
	int mask;
	vector<ll> F(1<<L);
	F[0]=1;
	
	FOR(i,M) {
		vector<ll> G(1<<L);
		G[0]=1;
		FOR(j,L) if(V[i][j]) {
			ll pat=p2[V[i][j]]-1;
			FOR(mask,1<<L) if(mask&(1<<j)) G[mask]=G[mask^(1<<j)]*pat%mo;
		}
		G[0]=0;
		
		vector<ll> F2=fft_or(F);
		vector<ll> G2=fft_or(G);
		FOR(mask,1<<L) (F2[mask]*=G2[mask])%=mo;
		F=fft_or(F2,1);
		F.resize(1<<L);
	}
	cout<<F[(1<<L)-1]<<endl;
}

まとめ

最初Mがすごい大きいかと勘違いしてしまった。