https://atcoder.jp/contests/abc246/tasks/abc246_f
この問題は数学的ですが、ということで単純に包除原理を使うだけです。
例1で考えると、文字が26種類しかないのでどの文字を使うかを2進数で表して、aが使われていたら最下位ビットを立てて、bが使われていたら下から2番目のビットを立てて、などとすると、ab : 011、ac : 101となります。2つの共通部分はビット論理積を取って、001となります。
abは2文字あることを011から1の数を数えて調べます。ビットを数える高速なアルゴリズムもありますが、それを使う必要はありません。
文字列の個数は共通部分の重複を除いて、となります。
計算量は、べき乗の計算にかかるので、です。
# coding: utf-8 # typewriter #################### library #################### def read_tuple(): return tuple(map(int, raw_input().split())) #################### process #################### def read_input(): N, L = read_tuple() S = [ raw_input() for _ in range(N) ] return (L, S) def count_bits(n): counter = 0 while n: if n & 1: counter += 1 n >>= 1 return counter def F(L, S): def g(ss): if len(ss) == 1: n = 0 for c in ss[0]: n |= 1 << (ord(c) - ord('a')) yield (-1, n) else: mid = len(ss) / 2 v1 = list(g(ss[:mid])) v2 = list(g(ss[mid:])) for sign1, n1 in v1: yield (sign1, n1) for sign2, n2 in v2: yield (sign1 * sign2, n1 & n2) for sign2, n2 in v2: yield (sign2, n2) s = 0 for sign, n in g(S): s -= sign * pow(count_bits(n), L, D) return s % D #################### main #################### D = 998244353 L, S = read_input() print F(L, S)