ABC246 F - typewriter

atcoder.jp

【問題】
・限られた文字だけが入力可能な、タイプライターが複数与えられる。
・各タイプライターは1種類だけ利用可能で、L文字入力する。
・L文字が何種類出来るか答えよ。

【考え方】
・ABしか入力できないタイプライターと、ACしか入力出来ないタイプライターで入力できる文字は
　それぞれAA、AB、BA、BBと、AA、AC、CA、CC。
　AAが重複している為、AAを取り除く必要がある。
・余事象で解ける。
・余事象では、いまいち良く分かっていないが、ベンズでいうと

　1つの円ー2つの円が重なっている場所＋3つの円が重なっている場所ー4つの円が重なっている場所＋5つの円が重なっている場所・・・・

　で重なっていない全ての面積が求まるらしい。
・上記をbit全探索を用いて実装する。

n,l=map(int,input().split())
typewriter=[input() for _ in range(n)]

typewriter_bin=[]

mod= 998244353 

for item in typewriter:
    tmp=0
    for i in range(ord("z")-ord("a")+1):
        if chr(ord("a")+i) in item:
            tmp+=pow(2,i)
    typewriter_bin.append(tmp)

ans=0
#タイプライターの組み合わせ
for i in range(1,2**n):
    kouho=[]
    for j in range(n):
        if i>>j&1==1:
            kouho.append(typewriter_bin[j])
    tmp=kouho[0]
    for item in kouho[1:]:
        tmp=tmp&item

    #足す
    tmp=str(bin(tmp)).count("1")

    if len(kouho)%2==1:
        ans+=pow(tmp,l,mod)
        ans%=mod

    #引く
    else:
        ans-=pow(tmp,l,mod)
        ans%=mod

print(ans%mod)