包除原理の基本を学ぶのに丁度良い問題.
\(\cup_{i \in N} X_{i}\) の要素の個数を数える問題. \(\Lambda \subset N\) に対して, $$\cap_{i \in \Lambda} X_{i}$$ を高速に求められれば十分.
実装:
使える文字の種類 \(\subset 26\) を高速に求めるには bit 演算が楽. また,整数型において \(-1\) は,すべての bit が 1になっている.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, l ;
cin >> n >> l;
vll ki(n); // kind
rep(i,n){
for(auto c:s[i]){
ki[i] |= 1ll << (c-'a');
}
}
mint ans = 0;
rep(t,(1LL<<n))if(t){
ll sig = 1;
if(pcntll(t) % 2 == 0) sig = -1;
ll x = -1;
rep(i,n) if(t>>i&1){
x &= ki[i];
}
ans += mint(sig)*mint(pcntll(x)).pow(l);
}
cout << ans.val() << endl;
return 0;
}