ABC246F - typewriter

考え方

包除原理
Editorial - AtCoder Beginner Contest 246

$k$段目のキーにどの文字が含まれるかを26bitで表す．

キーの組み合わせをbit全探索する（1 << 0〜1 << N - 1）．

各キーの組み合わせにおいて，選んだ全てのキーに共通して含まれる文字種の数を求める．これは，「キーに含まれる文字種を表すbit同士のandをとる→1の個数を数える」とすれば良い．

（選んだ全てのキーに共通して含まれる文字種の数）^Lを，選んだキーの数が奇数個なら加算し，偶数個なら減算する．

回答例

N, L = map(int, input().split())
key = []
for _ in range(N):
    s = input()
    bit = 0
    for ss in s:
        bit |= 1 << (ord(ss) - ord('a'))
    key.append(bit)

mod = 998244353
ans = 0
for comb in range(1, 1 << N):
    common_char = (1 << 26) - 1  # カッコは省略できない！
    for i in range(N):
        if (comb >> i) & 1:
            common_char &= key[i]
    cnt_key = sum((comb >> i) & 1 for i in range(N))
    cnt_char = sum((common_char >> i) & 1 for i in range(26))
    if cnt_key & 1:
        ans += pow(cnt_char, L, mod)
    else:
        ans -= pow(cnt_char, L, mod)
    ans %= mod

print(ans)

【参考】Submission #30640939 - AtCoder Beginner Contest 246

1が立っている数を計算するときに以下では上手く行かない．当たり前だが．

cnt_key = sum(comb & (1 << i) for i in range(N))
cnt_char = sum(common_char & (1 << i) for i in range(26))

フラグが立っているかを見るときはbit & (1 << i)でもよいが，これは0以外はTrueであることを利用している．1をカウントするときは，Trueが1になる(bit >> i) & 1を使わなければならない．