比赛链接：https://atcoder.jp/contests/agc046

A. Takahashikun, The Strider

题目链接：https://atcoder.jp/contests/agc046/tasks/agc046_a

题目大意：二维平面在原点，初始在原点，朝向南方，每次往面朝方向走一格，然后逆时针转 $X$ 度角，问经过几次后回到原点。

做法

为啥能这么快就做出来了？猜结论吗？

手动模拟一下，好像是最小的 $n$ 满足：$nX\equiv 0\mod 360$ 。

也就是：

等价于：$(n-1)t=2k\pi$ 或者 $nt=2k\pi$ 。

即：$\frac{2X(n-1)\pi}{360}=2k\pi\to (n-1)X=360k$ ，或者 $\frac{2Xn\pi}{360}=2k\pi\to nX=360k$ 。

同理：

等价于：$nt=2k\pi\to nX=360k$ 。

综上，$nX=360k$ 是回到原点的充要条件，显然就是上面说的那个东西。

1
2
3
4
5
6
7
8
9
#include<bits/stdc++.h>
using namespace std;
int gcd(int x, int y){return !x ? y : gcd(y % x, x);}
int main(){
    int n;
    cin >> n;
    cout << 360 / gcd(n, 360) << "\n";
    return 0;
}

B. Extension

题目链接：https://atcoder.jp/contests/agc046/tasks/agc046_b

题目大意：给定一个初始为白 $AB$ 的矩形，要求执行下列操作到 $CD$ 的矩形，问有多少种不同的染色。

  1. 在上面添加一行白色，并将这一行白色中添加任意一格黑色。
  2. 在右边添加一列白色，并将这一列白色中添加任意一格黑色。
我的做法

这种东西很典，就是给每种染色规定一个唯一的添加行列的顺序，然后直接 $dp$ 就行了。

首先肯定想着行列交换，显然在一种方案中行列能交换当且仅当后者不会在交点处涂黑，我们尽可能的让列靠前，对于所有 “ 行列 ” 无法交换的方案称为驻点。

问题来了，会有两个驻点方案吗？

不会，因为可以证明，以下构造出来的方案是驻点方案，且不是这个的方案都不是驻点方案：

对于任意一个染色方案，显然每一行或者每一列在生成的时候都会生成所在行或者列的第一个黑色。

知道每一行每一列生成的黑色是啥后，我们看当前的行数是否能生成下一列的黑色，能就生成，不能就先生成行的。

显然只要染色合法，就一定能生成一个方案，而且极其显然的是，一个方案能对应一个染色。

然后直接 $dp$ 计数就行了，时间复杂度：$O(n^2)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e3 + 5;
const LL mod = 998244353;
LL dp[N][N][2];
int A, B, C, D;
int main(){
    cin >> A >> B >> C >> D;
    dp[A][B][0] = 1ll;
    for(int i = A; i <= C; i++){
        for(int j = B; j <= D; j++){
            dp[i + 1][j][1] = (dp[i + 1][j][1] + (dp[i][j][0] + dp[i][j][1]) * j) % mod;
            if(i > A) dp[i][j + 1][0] = (dp[i][j + 1][0] + dp[i][j][1]) % mod;
            dp[i][j + 1][0] = (dp[i][j + 1][0] + dp[i][j][0] * i) % mod;
        }
    }
    cout << (dp[C][D][0] + dp[C][D][1]) % mod << "\n";
    return 0;
}
一个有意思的容斥做法

https://www.luogu.com.cn/article/pgbld0pu

先不管记重，$f_{i,j}=f_{i-1,j}j+f_{i,j-1}i$ ，假设前面是正确的，这里开始容斥，发现当 $(i,j)$ 不是黑色的时候会计两次。（这可以从转移分析得到）

所以正确的转移为 $f_{i,j}=f_{i-1,j}j+f_{i,j-1}i-f_{i-1,j-1}(i-1)(j-1)$ 。

C. Shift

题目链接：https://atcoder.jp/contests/agc046/tasks/agc046_c

题目大意：每次选择字符串中的 $i<j$ 满足 $s[i]=0,s[j]=1$ ，然后把 $1$ 放到 $0$ 左边，问经过至多 $K$ 次操作后能产生多少不同的字符串。

我的做法

注意到可以用 $0$ 给 $1$ 分段，用 $1$ 的数量变成数组 $A$，然后状态 $A$ 能到状态 $B$ 当且仅当：

  1. $\sum\limits_{i=1}^{len}|A_{i}-B_{i}|\le K$
  2. $\sum\limits_{i=1}^{j}B_{i}-A_{i}\ge 0$

直接 $dp[i][j][k]$ 计数就行了。

但是需要加个类似前缀和优化的东西保证时间复杂度是 $O(n^3)$ 的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 998244353;
const int N = 3e2 + 5;
void get_char_array(char *s){
    static char ss[N];
    cin >> ss;
    memcpy(s + 1, ss, sizeof(char) * (strlen(ss) + 1));
}
char st[N];
int n, m, a[N], b[N], K;
LL dp[N][N][N];
int main(){
    get_char_array(st); n = strlen(st + 1);
    cin >> K;
    {
        st[++n] = '0';
        for(int l = 1; l <= n; l++){
            int r = l;
            while(st[r] == '1') r++;
            a[++m] = r - l;
            l = r;
        }
    }
    for(int i = 1; i <= m; i++) b[i] = b[i - 1] + a[i];
    K = min(K, b[m]);
    dp[0][0][0] = 1ll;
    for(int i = 1; i <= m; i++){
        for(int j = 0; j <= K; j++){
            for(int k = j; k <= K; k++){
                dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k]) % mod;
                if(j) dp[i][j][k] = (dp[i][j][k] + dp[i][j - 1][k - 1]) % mod;
            }
        }
        for(int j = 1; j <= K; j++){
            for(int k = j; k <= K; k++){
                if(!dp[i - 1][j][k]) continue;
                for(int t = 1; t <= j && t <= a[i]; t++) dp[i][j - t][k] = (dp[i][j - t][k] + dp[i - 1][j][k]) % mod;
            }
        }
    }
    LL ans = 0ll;
    for(int i = 0; i <= K; i++) ans = (ans + dp[m][0][i]) % mod;
    cout << ans << "\n";
    return 0;
}

和官方做法基本一致。

D. Secret Passage

题目链接：https://atcoder.jp/contests/agc046/tasks/agc046_d

题目大意：你可以对 $01$ 字符串做以下操作若干次，问有多少个本质不同字符串：

若字符串长度 $\ge 2$ ，删除前面两个字符中的一个，并且将另外一个插入到字符串中的任意位置。

我的做法

首先一个典中典的事情，我们可以先不把没删除的字符插入，而是等到需要用时再插入，因此我们只关心在删除了一个前缀的情况下，我们手里能有多少个 $0$ ，多少个 $1$ 。

由于时间十分充裕，我们可以在 $O(n^3)$ 的时间处理出来。

现在的问题是，我们怎么在 $O(n^3)$ 的时间内，处理出所有可能的串？

首先先给所有的可能串分个类，根据其拥有的 $0$ 的个数和 $1$ 的个数，可以发现，在这两个确定后，我们其实只关心一个事情，能删的前缀的最大值是多少？

或者具体来说，在前面那个 $dp$ 做完后，我们实际上有一堆三元数：有多少个可以自由支配的 $0/1$ ，以及多长的后缀是固定的，可以看到在 $0/1$ 总数固定的情况下，后缀越短越好，因此总共有 $n^2$ 种不同的后缀。

这启示我们需要在 $O(n)$ 的时间针对一个种类求出答案，但是如果单独 $dp$ 这个复杂度寄中寄，注意到后缀长度是共同变量，启示我们一起处理一个大的 $dp$ ，然后每种是其中的部分和。

得到以下的 $dp$ ：

$f[i][j][k]$ 表示后缀匹配长度为 $i$ ，有 $j$ 个 $0$ ，$k$ 个 $1$ 的不同字符串数，匹配指最长的后缀满足是子序列，即能匹配就匹配。

对于三元数 $(j,k,len)$ ，显然其答案就是：$\sum\limits_{i=1}^{n-len+1}f[i][j][k]$ 。

总时间复杂度：$O(n^3)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 998244353;
const int N = 3e2 + 5;
void get_char_array(char *s){
    char ss[N];
    cin >> ss;
    memcpy(s + 1, ss, sizeof(char) * (strlen(ss) + 1));
}
bool dp[N][N][N];
LL sum[N][N][N];
char st[N];
int n, cnt0[N], cnt1[N], las[N][N];
int main(){
    get_char_array(st); n = strlen(st + 1);
    sum[n + 1][0][0] = 1ll;
    for(int i = n + 1; i >= 2; i--){//i = 1 no operator
        for(int j = 0; j <= n; j++){
            for(int k = 0; j + k <= n; k++){
                if(st[i - 1] == '0'){
                    sum[i - 1][j + 1][k] = (sum[i - 1][j + 1][k] + sum[i][j][k]) % mod;
                    sum[i][j][k + 1] = (sum[i][j][k + 1] + sum[i][j][k]) % mod;
                }
                else{
                    sum[i - 1][j][k + 1] = (sum[i - 1][j][k + 1] + sum[i][j][k]) % mod;
                    sum[i][j + 1][k] = (sum[i][j + 1][k] + sum[i][j][k]) % mod;
                }
            }
        }
    }
    for(int i = n; i >= 1; i--){
        cnt0[i] += cnt0[i + 1] + (st[i] == '0');
        cnt1[i] += cnt1[i + 1] + (st[i] == '1');
        las[cnt0[i]][cnt1[i]] = i;
    }
    dp[0][0][0] = 1;
    for(int i = 0; i <= n; i++){
        for(int j = i / 2; j >= 0; j--){
            for(int k = i / 2 - j; k >= 0; k--){
                if(!dp[i][j][k]) continue;
                {
                    int c0 = cnt0[i + 1] + j, c1 = cnt1[i + 1] + k;
                    if(c0 + c1) las[c0][c1] = max(las[c0][c1], i + 1);
                }

                if(i + 2 <= n){
                    if(st[i + 1] == '0' || st[i + 2] == '0') dp[i + 2][j + 1][k] = 1;
                    if(st[i + 1] == '1' || st[i + 2] == '1') dp[i + 2][j][k + 1] = 1;
                }
                if(j >= 1 && j + k >= 2) dp[i][j - 1][k] = 1;
                if(k >= 1 && j + k >= 2) dp[i][j][k - 1] = 1;
                if(i + 1 <= n){
                    if(j || k) dp[i + 1][j][k] = 1;
                    if(st[i + 1] == '0' && k) dp[i + 1][j + 1][k - 1] = 1;
                    if(st[i + 1] == '1' && j) dp[i + 1][j - 1][k + 1] = 1;
                }
            }
        }
    }
    LL ans = 0ll;
    for(int i = 0; i <= n; i++){
        for(int j = 0; i + j <= n; j++){
            if(!i && !j) continue;
            for(int k = las[i][j]; k >= 1; k--){
                ans = (ans + sum[k][i][j]) % mod;
            }
            ans--;
            ans++;
        }
    }
    cout << ans << "\n";
    return 0;
}

但感觉这种做法尽显暴力，等会看看正解是怎么优雅的做出这道题目的。

在此之前，我来证明一个在赛时没时间证明的想法：

删除任何一个前缀，假设可支配 $x$ 个 $0$ 和 $y$ 个 $1$ ，并且 $x+y$ 确定，那么 $x$ 的范围是个区间。

证明

我们可以考虑这么一个事情，给定一个前缀，给其标 $0/1$ ，$0$ 表示保留，$1$ 表示删掉，然后问这是否是一种合法的方案。

注：由于博主疏忽大意，后面记得根据语境区分 $0/1$ 指的是删除标记还是字符串的 $0/1$ 。

这个问题存在一种简单的判法，从左到右，如果接下来有两个字符，而且有至少一个 $1$ ，那么就直接对这两个字符操作，如果有两个 $0$ 或者只剩下一个字符，就搭一个 $1$ 进去操作（手中没有 $0$ 就不合法），等到没有剩余字符在前缀的时候，就拿手中的 $0$ 去消除手中的 $1$ 就行了（手中有 $1$ 但没 $0$ 就不合法），这样就能判断是否合法。

这个判法的证明也不难：

证明

对于 $2$ 个以上连续的 $0$ ，我们不妨设为 $L00R$ ，一定可以把这个过程分为 $L0,0R$ ，即一定是先做完 $L0$ ，再做 $0R$ （手中 $0,1$ 数量不会消失），注意到不合法当且仅当 $1$ 的数量不够了，因此我们希望在 $L0$ 处获得尽可能多的 $1$ ，对应的，上面的过程中遇到 $00$ ，我们都能进行这样子的划分，对于每一段，证明就变得十分的简单了，一定是：

$AB$ ，其中 $A$ 是长度为 $2len$ 的字符串，满足 $2i-1,2i$ 中至少有一个 $1$ ，$B$ 全是 $0$ ，这种段的最优策略是显然的，而显然，将这些最优策略拼起来就是整体最优的，而拼起来的策略就是上面的策略，所以就证明了上面的策略就是整体最优的。

证毕。

根据这个判法，我们可以将任意一种方案在每次只移动一个 $1$ 的情况下，变成下面这种方案：

假设总共有 $t$ 个 $1$ ，现在所有奇数位置放个 $1$ ，剩下的 $1$ 从左往右依次放在空着的偶数里。

鉴于这种移动可逆，所以所有的方案都可以通过这种方式互达，同时这种移动只会造成 $1$ 的变化，从而证明是个区间。

事实上，我们也可以加上加一个 $1$ 减一个 $1$ 的操作，从而得到在不固定 $x+y$ 的情况下 $(x+y,x)$ 的所在范围。

但是这个范围并没有很好，举个例子：

$111100110011001100$

至少需要 $4$ 步才能变成 $-1$ 的局面，而显然，利用这个例子，我们可以轻松的构造一个字符串使得 $x+y$ 相差为 $1$ 的 $x$ 的范围差别很大（指上下界差别很大）。

那难道是在 $x+y=\left\lceil\frac{n}{2}\right\rceil$ 时才会发生这种情况吗？

不对，可以通过类似的方法，构造出 $x+y-\left\lceil\frac{n}{2}\right\rceil$ 任意大的错误例子：

核心思路是：开头若干个 $11$ 提供多出来的 $1$ ，然后一个单独的 $0$ 消耗 $1$ ，然后若干个 $0110$ 加大相邻两个单独的 $1$ 之间的距离，然后再放一个单独的 $0$ 循环往复。

上面例子拆分就是：$11/11/0/0110/0110/0110/0$ ，为什么这个需要花多步呢？

因为每次尝试把 $1$ 放到 $0$ 上面时，会发现影响只是整体右移，不会导致最后手里有多余的 $1$ （因为注意到如果最后手中有多余的 $1$ ，就可以删除这个 $1$ 证明在 $x+y$ 插值绝对值不超过 $1$ 的情况下， $x$ 的上下界差值的绝对值也不超过 $1$）。

这里实操一下就知道了：

$11/11/0/0110/0110/0110/0\to 10/11/1/0110/0110/0110/0\to 10/11/1011/0/0110/0110/0$

而最后能多出 $1$ 一定是通过移动把两个单独的 $0$ 放到了一起，然后再放一个 $1$ 同时把两个单独的 $0$ 用一个 $1$ 解决了，从而节省一个 $1$ 。但是这个移动的过程所花费的大量的移动就已经足够把相邻 $x+y$ 的 $x$ 的上下界拉得足够大了。

所以不固定 $x+y$ 的情况下 $(x+y,x)$ 的范围不一定是好的。

虽然但是，上面的反例似乎只是说明这种方法无法证明范围是好的，也许范围就是好的，或者部分好的，只是方法问题？不知道，感觉这个的证明或者证伪已经超出了博主目前的实力范围了。

但是还是用代码验证一下刚才的那个说法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 998244353;
const int N = 3e2 + 5;
void get_char_array(char *s){
    char ss[N];
    cin >> ss;
    memcpy(s + 1, ss, sizeof(char) * (strlen(ss) + 1));
}
bool dp[N][N][N];
char st[N];
int n, cnt0[N], cnt1[N], las[N][N];
int ll[N], rr[N];
int main(){
    get_char_array(st); n = strlen(st + 1);
    for(int i = n; i >= 1; i--){
        cnt0[i] += cnt0[i + 1] + (st[i] == '0');
        cnt1[i] += cnt1[i + 1] + (st[i] == '1');
        las[cnt0[i]][cnt1[i]] = i;
    }
    dp[0][0][0] = 1;
    for(int i = 0; i <= n; i++){
        for(int j = i / 2; j >= 0; j--){
            for(int k = i / 2 - j; k >= 0; k--){
                if(!dp[i][j][k]) continue;
                {
                    int c0 = cnt0[i + 1] + j, c1 = cnt1[i + 1] + k;
                    if(c0 + c1) las[c0][c1] = max(las[c0][c1], i + 1);
                }

                if(i + 2 <= n){
                    if(st[i + 1] == '0' || st[i + 2] == '0') dp[i + 2][j + 1][k] = 1;
                    if(st[i + 1] == '1' || st[i + 2] == '1') dp[i + 2][j][k + 1] = 1;
                }
                if(j >= 1 && j + k >= 2) dp[i][j - 1][k] = 1;
                if(k >= 1 && j + k >= 2) dp[i][j][k - 1] = 1;
                if(i + 1 <= n){
                    if(j || k) dp[i + 1][j][k] = 1;
                    if(st[i + 1] == '0' && k) dp[i + 1][j + 1][k - 1] = 1;
                    if(st[i + 1] == '1' && j) dp[i + 1][j - 1][k + 1] = 1;
                }
            }
        }
    }
    for(int i = 1; i <= n / 2; i++) ll[i] = n + 1, rr[i] = 0;
    for(int l = 0; l <= n / 2; l++){
        for(int r = 0; l + r <= n / 2; r++){
            if(dp[n][l][r]) ll[l + r] = min(ll[l + r], l), rr[l + r] = max(rr[l + r], l);
        }
    }
    for(int i = 1; i <= n / 2; i++){
        cout << "x + y = " << i << " : [" << ll[i] << " , " << rr[i] << "]" << "\n";
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
input:

111111110011001100110011001100110001100110011001100110011000110011001100110011001100011001100110011001100110

output:
x + y = 1 : [0 , 1]
x + y = 2 : [0 , 2]
x + y = 3 : [0 , 3]
x + y = 4 : [0 , 4]
x + y = 5 : [0 , 5]
x + y = 6 : [0 , 6]
x + y = 7 : [0 , 7]
x + y = 8 : [0 , 8]
x + y = 9 : [0 , 9]
x + y = 10 : [0 , 10]
x + y = 11 : [0 , 11]
x + y = 12 : [0 , 12]
x + y = 13 : [0 , 13]
x + y = 14 : [0 , 14]
x + y = 15 : [0 , 15]
x + y = 16 : [0 , 16]
x + y = 17 : [0 , 17]
x + y = 18 : [0 , 18]
x + y = 19 : [0 , 19]
x + y = 20 : [0 , 20]
x + y = 21 : [0 , 21]
x + y = 22 : [0 , 22]
x + y = 23 : [0 , 23]
x + y = 24 : [0 , 24]
x + y = 25 : [0 , 25]
x + y = 26 : [0 , 26]
x + y = 27 : [0 , 27]
x + y = 28 : [0 , 28]
x + y = 29 : [0 , 29]
x + y = 30 : [0 , 30]
x + y = 31 : [0 , 31]
x + y = 32 : [0 , 32]
x + y = 33 : [0 , 33]
x + y = 34 : [0 , 34]
x + y = 35 : [0 , 35]
x + y = 36 : [0 , 36]
x + y = 37 : [0 , 37]
x + y = 38 : [0 , 38]
x + y = 39 : [0 , 39]
x + y = 40 : [0 , 40]
x + y = 41 : [0 , 41]
x + y = 42 : [0 , 42]
x + y = 43 : [0 , 43]
x + y = 44 : [0 , 44]
x + y = 45 : [0 , 45]
x + y = 46 : [0 , 46]
x + y = 47 : [0 , 47]
x + y = 48 : [0 , 48]
x + y = 49 : [0 , 49]
x + y = 50 : [0 , 50]
x + y = 51 : [0 , 51]
x + y = 52 : [0 , 52]
x + y = 53 : [7 , 45]
x + y = 54 : [14 , 38]

至少从例子上来看，范围不是绝对好的，至于是不是部分好的，这就不在我能力范围之内了。

证完了，看看题解。

看完了，基本一致。

但是看到一份很短的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
void add(int &x,int v){((x+=v)>=MOD)&&(x-=MOD);}
int n,ok[305][305][305],dp[305][305][305],res;
char s[305];
int main(){
	scanf("%s",s+1);n=strlen(s+1);ok[0][0][0]=1;
	for(int i=1;i<=n;i++)for(int j=n;~j;j--)for(int k=n;~k;k--){
		ok[i][j][k]|=ok[i-1][j][k];
		ok[i][j][k]|=ok[i][j+1][k];
		ok[i][j][k]|=ok[i][j][k+1];
		if(j&&i>=2&&(s[i]=='0'||s[i-1]=='0'))ok[i][j][k]|=ok[i-2][j-1][k];
		if(k&&i>=2&&(s[i]=='1'||s[i-1]=='1'))ok[i][j][k]|=ok[i-2][j][k-1];
		if(j&&s[i]=='0')ok[i][j][k]|=ok[i-1][j-1][k+1];
		if(k&&s[i]=='1')ok[i][j][k]|=ok[i-1][j+1][k-1];
	}
	dp[n][0][0]=1;
	for(int i=n;i;i--)for(int j=0;j<=n;j++)for(int k=0;k<=n;k++){
		add(dp[i-1][j][k],dp[i][j][k]);
		if(s[i]=='0')add(dp[i][j][k+1],dp[i][j][k]);
		if(s[i]=='1')add(dp[i][j+1][k],dp[i][j][k]);
	}
	for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)for(int k=0;k<=n;k++)
		if(ok[i][j][k])add(res,dp[i][j][k]);
	add(res,MOD-1);printf("%d\n",res);
	return 0;
}
//https://www.luogu.com.cn/article/vjo8hwnx

很厉害啊，就算不压行也比我的短。

可以从我的做法导出这个写法是对的。但考场上我是不会这么写的，主要是不稳，本来做法就需要证明，现在还要写一份需要证明的代码，这在考场上性价比是不高的，万一代码实际上计多了或少了，就又得花时间，所以我不会在考场上写这种代码。

但是在考场外用来观赏或者炫技的话，美观度确实是拉满了，可以学习一下。

至于为什么这样写是对的，不难证明，在此就不再赘述了。