# 【题目】typewriter

AtCoder Beginner Contest 246

F - typewriter

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : $500$ points

### Problem Statement

We have a typewriter with $N$ rows. The keys in the ii-th row from the top can type the characters in a string $S_i$.

Let us use this keyboard to enter a string, as follows.

• First, choose an integer $1 \le k \le N$.
• Then, start with an empty string and only use the keys in the $k$-th row from the top to enter a string of length exactly $L$.

How many strings of length $L$ can be entered in this way? Since the answer can be enormous, print it modulo $998244353$.

### Constraints

• $N$ and $L$ are integers.
• $1 \le N \le 18$
• $1 \le L \le 10^9$
• $S_i$ is a (not necessarily contiguous) non-empty subsequence of abcdefghijklmnopqrstuvwxyz.

### Input

Input is given from Standard Input in the following format:

$N$ $L$
$S_1$
$S_2$
$\dots$
$S_N$

2 2
ab
ac

### Sample Output 1

7

We can enter seven strings: aa, ab, ac, ba, bb, ca, cc.

4 3
abcdefg
hijklmnop
qrstuv
wxyz

1352

5 1000000000
abc
acde
cefg
abcfh
dghi

### Sample Output 3

346462871

Be sure to print the answer modulo $998244353$.

### 我的笔记

#### 容斥原理

{\displaystyle {\begin{aligned}\left|\bigcup _{i=1}^{n}A_{i}\right|={}&\sum _{i=1}^{n}|A_{i}|-\sum _{1\leq i<j\leq n}|A_{i}\cap A_{j}|+\sum _{1\leq i<j<k\leq n}|A_{i}\cap A_{j}\cap A_{k}|-\cdots +(-1)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|.\end{aligned}}}

（图片和公式来源：维基百科，使用 CC BY-NC-SA 4.0 许可）

#### 题目转化

$+$ 第 $1$ 行按键的种数 $+$ 第 $2$ 行按键的种数 $+$ 第 $3$ 行按键的种数

$-$ 第 $1、2$ 行按键能组合出的种数 $-$ 第 $1、3$ 行按键能组合出的种数 $-$ 第 $2、3$ 行按键能组合出的种数

$+$ 第 $1、2、3$ 行按键能组合出的种数

### 源码

#include <bits/stdc++.h>
#define MOD 998244353

using namespace std;

long long fast_pow(long long a, long long b)
{
a %= MOD;
long long ans = 1;
while (b)
{
if (b % 2)
{
ans = ans * a % MOD;
}
b /= 2;
a = a * a % MOD;
}
return ans;
}

int main()
{
int N, L;
cin >> N >> L;
bool row[18][26];
memset(row, false, sizeof(row));
for (int i = 0; i < N; i++)
{
string keys;
cin >> keys;
for (auto &key : keys)
row[i][key - 'a'] = true;
}
long long ans = 0;
for (int i = 1; i < (1 << N); i++)
{
bool these_rows[26];
memset(these_rows, true, sizeof(these_rows));
int selected_row_cnt = 0, selected_key_cnt = 0;
for (int j = 0; j < N; j++)
{
if (i & (1 << j))
{
selected_row_cnt++;
for (int k = 0; k < 26; k++)
{
these_rows[k] &= row[j][k];
}
}
}
for (int i = 0; i < 26; i++)
{
if (these_rows[i])
selected_key_cnt++;
}
if (selected_row_cnt % 2)
{
ans += fast_pow(selected_key_cnt, L);
ans %= MOD;
}
else
{
ans += MOD - fast_pow(selected_key_cnt, L);
ans %= MOD;
}
}
cout << ans << endl;
return 0;
}