ABC246F typewriter Solution

更好的阅读体验戳此进入

题面

给定 $n$$n$ 个字符串，字符集为小写字母，可以任意选择一个字符串，作为字符库，然后（可多次选择同一字符）任意组成长度为 $l$$l$ 的字符串，求一共能形成多少种长度为 $l$$l$ 的字符串。

Solution

容斥较为显然，显然最终答案也就是，用任意一个字符集形成的字符串减去任意两个的加上任意三个...于是我们考虑令全集为 $S=2^n-1$$S = 2^n - 1$ 然后对其进行枚举子集，二进制第 $i$$i$ 位为 $1$$1$ 或 $0$$0$ 代表是否考虑这个数，所以枚举的时候直接 __builtin_popcount() 算一下个数，奇数代表加，反之减。然后对于每一个字符串，因为字符集较小，也用一个 int 的二进制表示是否存在对应的字符，然后把需要的字符串都与起来，设数量为 $\xi$$\xi$，则此次运算的字符集大小则为 $\xi$$\xi$，所以此次答案为 ${\xi }^l$$\xi^l$，加减考虑好即可。

Code

xxxxxxxxxx
85
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12
using namespace __gnu_pbds;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define MOD 998244353
24

25
template<typename T = int>
26
inline T read(void);
27

28
int N, L;
29
int str[20];
30
int 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
}
40
ll 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

49
int 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

71
template<typename T>
72
inline 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
}

UPD

update-2022_10_21 初稿