[ABC246] F - typewriter

[Q] https://atcoder.jp/contests/abc246/tasks/abc246_f

考察

Q. 入力例1
N=2 L=2
ab
ac

S0 = "ab" を選んだ場合
aa, ab, ba, bb がユニーク。 ans += 4 // 4

S1 = "ac" を選んだ場合
aa, ac, ca, cc がユニーク。 ans += 4 // 8

S0&S1 = "a" を選んだ場合
aa が重複している。 ans -= 1 // 7

ans = 7

1. S0を見て、(文字数^L)がありうる組み合わせで、ユニーク。加算する。
2. S0&S1を見て、(重複する文字数^L)が重複なので、除く。
3. S0&S1&S2を見て、(重複文字数^L)が除きすぎているので補正加算。
4. S0&S1&S2&S3を見て、(重複文字数^L)が補正加算されすぎているので補正減算。
...
つまりbitDPで包除原理を適応する。

実装

ll H[20];
ll N, L;

int main() {
 cincout();

 cin >> N >> L;
 string S;
 rep(i, N) {
   cin >> S;
   ll hash = 0;
   for (auto s : S) {
     hash |= 1 << (s - 'a');
   }
   H[i] = hash;
 }

 mint ans = 0;
 mint mods[30];
 rep(i, 26) {  // i^L
   mods[i + 1] = modpow(i + 1, L, MOD);
 }
 rep(i, (1 << N)) {
   if (i == 0) continue;
   ll hash = (1 << 26) - 1;
   rep(j, N) {
     if (is_pop(i, j)) hash &= H[j];
   }
   ll bp = __builtin_popcount(hash);
   if (__builtin_popcount(i) % 2)
     ans += mods[bp];
   else
     ans -= mods[bp];
 }
 cout << ans << endl;
}

https://atcoder.jp/contests/abc246/submissions/30651796