Codeforces ECR #119 : G. Subsequences Galore

これは本番中に解けた。
https://codeforces.com/contest/1620/problem/G

問題

N個の文字列が与えられる。
それぞれはアルファベット順にソートされている。

文字列集合に対するスコアは、少なくとも1つ以上の(不連続でもよい)部分文字列である文字列数とする。
N個の文字列の冪集合2^N通りに対し、それぞれスコアを求めよ。

解法

包除原理と高速ゼータ変換で解く。
文字列集合に対し、各文字の頻度の最小値を取って、全文字列の部分列の個数を数えよう。
その後、包除原理と高速ゼータ変換を行えば、1個以上の文字列の部分文字列を数えることができる。

int N;
int C[23][26];
ll dp[1<<23];
ll F[1<<23];
ll G[1<<23];
const ll mo=998244353;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>s;
		FORR(c,s) C[i][c-'a']++;
	}
	int mask,mask2;
	FOR(mask,1<<N) if(mask) {
		int C2[26];
		FOR(j,26) C2[j]=1<<20;
		FOR(i,N) if(mask&(1<<i)) {
			FOR(j,26) C2[j]=min(C2[j],C[i][j]);
		}
		F[mask]=1;
		FOR(j,26) (F[mask]*=C2[j]+1)%=mo;
		x=__builtin_popcount(mask);
		if(x%2==0) F[mask]=mo-F[mask];
	}
	
	FOR(i,N) {
		FOR(mask,1<<N) if(mask&(1<<i)) (F[mask]+=F[mask^(1<<i)])%=mo;
	}
	
	ll ret=0;
	FOR(mask,1<<N) {
		int k=0;
		int s=0;
		FOR(i,N) if(mask&(1<<i)) k++,s+=i+1;
		ret^=F[mask]*k*s;
	}
	cout<<ret<<endl;
}

まとめ

ECRのボス問にしてはすんなり。