给定
容斥较为显然,显然最终答案也就是,用任意一个字符集形成的字符串减去任意两个的加上任意三个...于是我们考虑令全集为 __builtin_popcount()
算一下个数,奇数代表加,反之减。然后对于每一个字符串,因为字符集较小,也用一个 int
的二进制表示是否存在对应的字符,然后把需要的字符串都与起来,设数量为
xxxxxxxxxx
851
2
3
4
5
6
7
8
9
10
11using namespace std;
12using namespace __gnu_pbds;
13
14mt19937 rnd(random_device{}());
15int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16bool rnddd(int x){return rndd(1, 100) <= x;}
17
18typedef unsigned int uint;
19typedef unsigned long long unll;
20typedef long long ll;
21typedef long double ld;
22
23
24
25template<typename T = int>
26inline T read(void);
27
28int N, L;
29int str[20];
30int readStr(void){
31 int ret(0);
32 char c = getchar();
33 while(!islower(c))c = getchar();
34 vector < int > val;
35 while(islower(c)){
36 ret |= 1 << (c - 'a');
37 c = getchar();
38 }return ret;
39}
40ll qpow(ll a, ll b){
41 ll ret(1), mul(a);
42 while(b){
43 if(b & 1)ret = ret * mul % MOD;
44 b >>= 1;
45 mul = mul * mul % MOD;
46 }return ret;
47}
48
49int main(){
50 N = read(), L = read();
51 ll ans(0);
52 for(int i = 1; i <= N; ++i)str[i] = readStr();
53 // for(int i = 1; i <= N; ++i)
54 // cout << bitset < 32 > (str[i]) << endl;
55 int Smx = (1 << N) - 1;
56 // cout << "Smx" << bitset < 32 > (Smx) << endl;
57 for(int S = Smx; S; S = (S - 1) & Smx){
58 // cout << "S:" << bitset < 32 > (S) << endl;
59 int cnt = __builtin_popcount(S);
60 int tot((1 << 26) - 1);
61 for(int i = 0; i <= N - 1; ++i)
62 if((1 << i) & S)tot &= str[i + 1];
63 // cout << "tot:" << bitset < 32 > (tot) << endl;
64 ans = (ans + qpow(__builtin_popcount(tot), L) * ((cnt & 1) ? 1 : -1) + MOD) % MOD;
65 }
66 printf("%lld\n", ans);
67 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
68 return 0;
69}
70
71template<typename T>
72inline T read(void){
73 T ret(0);
74 short flag(1);
75 char c = getchar();
76 while(c != '-' && !isdigit(c))c = getchar();
77 if(c == '-')flag = -1, c = getchar();
78 while(isdigit(c)){
79 ret *= 10;
80 ret += int(c - '0');
81 c = getchar();
82 }
83 ret *= flag;
84 return ret;
85}
update-2022_10_21 初稿