ABC246F typewriter Solution

• ABC246F typewriter Solution
  • 更好的阅读体验戳此进入
  • 题面
  • Solution
  • Code
  • UPD

更好的阅读体验戳此进入

题面

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

Solution

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

Code

#define _USE_MATH_DEFINES
#include <bits/extc++.h>

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

using namespace std;
using namespace __gnu_pbds;

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

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

#define MOD 998244353

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

int N, L;
int str[20];
int readStr(void){
    int ret(0);
    char c = getchar();
    while(!islower(c))c = getchar();
    vector < int > val;
    while(islower(c)){
        ret |= 1 << (c - 'a');
        c = getchar();
    }return ret;
}
ll qpow(ll a, ll b){
    ll ret(1), mul(a);
    while(b){
        if(b & 1)ret = ret * mul % MOD;
        b >>= 1;
        mul = mul * mul % MOD;
    }return ret;
}

int main(){
    N = read(), L = read();
    ll ans(0);
    for(int i = 1; i <= N; ++i)str[i] = readStr();
    // for(int i = 1; i <= N; ++i)
    //     cout << bitset < 32 > (str[i]) << endl;
    int Smx = (1 << N) - 1;
    // cout << "Smx" << bitset < 32 > (Smx) << endl;
    for(int S = Smx; S; S = (S - 1) & Smx){
        // cout << "S:" << bitset < 32 > (S) << endl;
        int cnt = __builtin_popcount(S);
        int tot((1 << 26) - 1);
        for(int i = 0; i <= N - 1; ++i)
            if((1 << i) & S)tot &= str[i + 1];
        // cout << "tot:" << bitset < 32 > (tot) << endl;
        ans = (ans + qpow(__builtin_popcount(tot), L) * ((cnt & 1) ? 1 : -1) + MOD) % MOD;
    }
    printf("%lld\n", ans);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template<typename T>
inline T read(void){
    T ret(0);
    short flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

UPD

update-2022_10_21 初稿