杂题小记（2023.03.02-03）

更好的阅读体验戳此进入

[AGC020E] Encoding Subsets

题面

我们定义一个 01 串的压缩是满足如下方式的字符串变化过程：

• $0\to 0,1\to 1$$0\rightarrow 0,1\rightarrow 1$

• 如果 $A\to P,B\to Q$$A\rightarrow P,B\rightarrow Q$ 合法，那么 $A+B\to P+Q$$A+B\rightarrow P+Q$ 也合法（其中 $+$$+$ 代表字符串拼接）

• 如果 $S=\underset{n\text{个}(n\ge 2)}{\underbrace{A+A+\cdots +A}}$$S=\underbrace{A+A+\cdots+A}_{n\text{个}(n\ge 2)}$，那么 $S\to (A\times n)$$S\rightarrow(A\times n)$ 也合法（其中 (, ), × 为字符，$n$$n$ 为数字，算作一个字符，即使其中有 $0/1$$0/1$）

我们同时定义 $01$$01$ 串 $B$$B$ 是 $A$$A$ 的子集当且仅当：

• $|A|=|B|$$|A|=|B|$

• $\mathrm{\forall }{B}_i=1,A_i=1$$\forall B_i=1,A_i=1$

现在给你一个 $01$$01$ 串 $S$$S$，问它所有的子集的合法变化结果数的总和为多少。

答案对 $998244353$$998244353$ 取模。

Solution

小清新记忆化搜索维护 DP，考虑令 $f(S)$$f(S)$ 表示字符串状态为 $S$$S$ 时的方案数，考虑对于状态 $S$$S$ 中的最后一个字符，如果我们不将其进行压缩，

Code

xxxxxxxxxx
71
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.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 void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
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 (998244353ll)
24

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

28
string S;
29
map < pair < __int128_t, int >, ll > mp;
30

31
ll dfs(__int128_t S, int len){
32
    if(!len)return 1;
33
    if(mp.find({S, len}) != mp.end())return mp[{S, len}];
34
    ll ret(0);
35
    (ret += dfs(S >> 1, len - 1) * (S & 1 ? 2 : 1) % MOD) %= MOD;
36
    __int128_t siz(0), cur(0);
37
    for(int slen = 1; slen <= len; ++slen){
38
        (siz <<= 1) |= 1, cur = S & siz;
39
        for(int rlen = slen << 1; rlen <= len; rlen += slen){
40
            cur &= S >> (rlen - slen);
41
            (ret += dfs(cur, slen) * dfs(S >> rlen, len - rlen) % MOD) %= MOD;
42
        }
43
    }return mp[{S, len}] = ret;
44
}
45

46
int main(){
47
    cin >> S;
48
    int N = S.length();
49
    __int128_t cur(0);
50
    for(int i = 0; i < N; ++i)
51
        cur |= (__int128_t)(S.at(i) == '1') << i;
52
    printf("%lld\n", dfs(cur, N));
53
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
54
    return 0;
55
}
56

57
template < typename T >
58
inline T read(void){
59
    T ret(0);
60
    int flag(1);
61
    char c = getchar();
62
    while(c != '-' && !isdigit(c))c = getchar();
63
    if(c == '-')flag = -1, c = getchar();
64
    while(isdigit(c)){
65
        ret *= 10;
66
        ret += int(c - '0');
67
        c = getchar();
68
    }
69
    ret *= flag;
70
    return ret;
71
}

题面

Solution

Code

xxxxxxxxxx
1
1

题面

Solution

Code

xxxxxxxxxx
1
1

题面

Solution

Code

xxxxxxxxxx
1
1

题面

Solution

Code

xxxxxxxxxx
1
1

题面

Solution

Code

xxxxxxxxxx
1
1

UPD

update-2023__ 初稿