F - typewriter Editorial by physics0523
この問題は、 包除原理 を使って解くことができます。
例えば、 \(N=3\) の場合なら、
\((\) \(1\) 段目、 \(2\) 段目、 \(3\) 段目の少なくとも \(1\) 段以上で入力できる文字列の総数 \() = \)
\(+\) \(1\) 段目で入力できる文字列
\(+\) \(2\) 段目で入力できる文字列
\(+\) \(3\) 段目で入力できる文字列
\(-\) \(1\) 段目、 \(2\) 段目双方で入力できる文字列
\(-\) \(1\) 段目、 \(3\) 段目双方で入力できる文字列
\(-\) \(2\) 段目、 \(3\) 段目双方で入力できる文字列
\(+\) \(1\) 段目、 \(2\) 段目、 \(3\) 段目のすべてで入力できる文字列
となります。( \(N\) が小さい場合、ベン図のイメージを持つのも理解の助けになるでしょう。)
\(N \le 18\) と小さいので、着目する段の集合 \(2^N-1\) 通りを全探索することを考えます。このとき、以下の問題が解ければ元の問題も解けることになります。
\(A_1\) 段目、 \(A_2\) 段目、 \(\dots A_k\) 段目のすべてで入力できる文字列は何通りか? (なお、 \(A\) に含まれない段についてはその段で入力できてもできなくてもよい。)
文字列 \(S\) が条件を満たす必要十分条件を求めます。
明らかに、 \(S\) に含まれる全ての文字は、 \(A\) に含まれる全ての段で入力可能であるべきです。逆に、 \(S\) が \(A\) に含まれる全ての段で入力可能な文字しか含まないならば \(S\) は条件を満たします。
よって、この問題の答えは ( \(A\) に含まれる全ての段で入力可能な文字の種類数) \(^L\) となります。
これを \(2^N-1\) 通り全てについて包除原理に従って適切に足し引きしていくことで、この問題に正解できます。
計算量は \(O(2^N (N + \log L))\) です。
なお、実装例では「\(A\) に含まれる全ての段で入力可能な文字の種類数」を bit 演算にて高速に求めています。
実装例(C++):
#include<bits/stdc++.h>
#define mod 998244353
using namespace std;
long long power(long long a,long long b){
long long x=1,y=a;
while(b>0){
if(b&1ll){
x=(x*y)%mod;
}
y=(y*y)%mod;
b>>=1;
}
return x%mod;
}
int main(){
int n,k;
cin >> n >> k;
vector<int> v(n,0);
for(int i=0;i<n;i++){
string s;
cin >> s;
for(auto &nx : s){v[i]|=(1<<(nx-'a'));}
}
long long res=0;
for(int i=1;i<(1<<n);i++){
int ch=(1<<26)-1;
for(int j=0;j<n;j++){
if(i&(1<<j)){ch&=v[j];}
}
int pc=__builtin_popcount((unsigned int)ch);
if(__builtin_popcount((unsigned int)i)%2){res+=power(pc,k);res%=mod;}
else{res+=(mod-power(pc,k));res%=mod;}
}
cout << res << '\n';
return 0;
}
posted:
last update: