AtCoder Beginner Contest 246 Solution

更好的阅读体验戳此进入

题面链接

题面 Luogu 链接

A - Four Points

题面

给定矩形三个点坐标，求另一个点的坐标。

Solution

显然四个点横纵坐标分别两两相等，三个横坐标异或，三个纵坐标异或即可。

Code

xxxxxxxxxx
47
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
template<typename T = int>
24
inline T read(void);
25

26
int main(){
27
    int x1 = read(), y1 = read(), x2 = read(), y2 = read(), x3 = read(), y3 = read();
28
    printf("%d %d\n", x1 ^ x2 ^ x3, y1 ^ y2 ^ y3);
29
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
30
    return 0;
31
}
32

33
template<typename T>
34
inline T read(void){
35
    T ret(0);
36
    short flag(1);
37
    char c = getchar();
38
    while(c != '-' && !isdigit(c))c = getchar();
39
    if(c == '-')flag = -1, c = getchar();
40
    while(isdigit(c)){
41
        ret *= 10;
42
        ret += int(c - '0');
43
        c = getchar();
44
    }
45
    ret *= flag;
46
    return ret;
47
}

B - Get Closer

题面

给定一个向量的坐标表示，求同向模长为 $1$$1$ 的向量坐标。

Solution

语法题没营养，为了凑齐一套题去写的。

Code

xxxxxxxxxx
49
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
template<typename T = int>
24
inline T read(void);
25

26
int main(){
27
    int x = read(), y = read();
28
    ld base = sqrtl((ld)x * x + (ld)y * y);
29
    printf("%.8Lf %.8Lf\n", (ld)x / base, (ld)y / base);
30

31
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
32
    return 0;
33
}
34

35
template<typename T>
36
inline T read(void){
37
    T ret(0);
38
    short flag(1);
39
    char c = getchar();
40
    while(c != '-' && !isdigit(c))c = getchar();
41
    if(c == '-')flag = -1, c = getchar();
42
    while(isdigit(c)){
43
        ret *= 10;
44
        ret += int(c - '0');
45
        c = getchar();
46
    }
47
    ret *= flag;
48
    return ret;
49
}

C - Coupon

题面

$n$$n$ 个物品第 $i$$i$ 个价格为 $a_i$$a_i$，有 $k$$k$ 张 $x$$x$ 元优惠券，可以叠加，但不能分裂开使用，求全部购买的最少花费。

Solution

对于所有 $a_i\ge x$$a_i \ge x$ 一直使用优惠券直到 $a_i<x$$a_i \lt x$，然后降序排序用剩余的 $k$$k$ 个券把前 $k$$k$ 个抵消，后面的求和即为答案。

Code

xxxxxxxxxx
53
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
template<typename T = int>
24
inline T read(void);
25

26
int a[210000];
27

28
int main(){
29
    int N = read(), K = read(), X = read();
30
    for(int i = 1; i <= N; ++i){a[i] = read();while(K && a[i] >= X)--K, a[i] -= X;}
31
    sort(a + 1, a + N + 1, greater < int >());
32
    ll ans(0);
33
    for(int i = K + 1; i <= N; ++i)ans += a[i];
34
    printf("%lld\n", ans);
35
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
36
    return 0;
37
}
38

39
template<typename T>
40
inline T read(void){
41
    T ret(0);
42
    short flag(1);
43
    char c = getchar();
44
    while(c != '-' && !isdigit(c))c = getchar();
45
    if(c == '-')flag = -1, c = getchar();
46
    while(isdigit(c)){
47
        ret *= 10;
48
        ret += int(c - '0');
49
        c = getchar();
50
    }
51
    ret *= flag;
52
    return ret;
53
}

D - 2-variable Function

题面

存在函数 $f(a,b)=a^3+a^{2}b+a{b}^2+b^3$$f(a, b) = a^3 + a^2b + ab^2 + b^3$，要求 $a,b\ge 0$$a, b \ge 0$，给定 $n$$n$，求最小的 $f(a,b)$$f(a, b)$ 满足 $f(a,b)\ge n$$f(a, b) \ge n$。$n\le {10}^{18}$$n \le 10^{18}$。

Solution

显然 $a,b$$a, b$ 的范围不超过 ${10}^6$$10^6$，则可以枚举 $a$$a$，二分 $b$$b$，取最小值即可。

对于二分 $b$$b$ 的单调性证明，可以考虑固定 $a$$a$ 为参数，则有函数 $f(b)=b^3+a{b}^2+a^{2}b+a^3$$f(b) = b^3 + ab^2 + a^2b + a^3$，三次函数不好操作，所以考虑求导，显然 $f^{\prime }(b)=3b^2+2ab+a^2$$f'(b) = 3b^2 + 2ab + a^2$，因为 $a,b$$a, b$ 非负，所以显然导函数 $f^{\prime }(b)\ge 0$$f'(b) \ge 0$，所以范围内函数取值单调递增，于是可以二分。

或者不进行二分，根据单调性，显然 $a$$a$ 减小时 $b$$b$ 不会比上次更大，所以写个双指针枚举，$a$$a$ 升序，$b$$b$ 降序，小于 $n$$n$ 时直接 break 即可。

Code

xxxxxxxxxx
62
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
template<typename T = int>
24
inline T read(void);
25

26
ll Func(int a, int b){
27
    return (ll)a * a * a + (ll)a * a * b + (ll) a * b * b + (ll)b * b * b;
28
}
29

30
int main(){
31
    ll N = read<ll>();
32
    ll mn(LLONG_MAX);
33
    for(int x = 0; x <= (int)1e6; ++x){
34
        int l = 0, r = (int)1e6;
35
        ll cur(-1);
36
        while(l <= r){
37
            int mid = (l + r) >> 1;
38
            ll tmp = Func(x, mid);
39
            if(tmp >= N)cur = tmp, r = mid - 1;
40
            else l = mid + 1;
41
        }
42
        mn = min(mn, cur);
43
    }printf("%lld\n", mn);
44
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
45
    return 0;
46
}
47

48
template<typename T>
49
inline T read(void){
50
    T ret(0);
51
    short flag(1);
52
    char c = getchar();
53
    while(c != '-' && !isdigit(c))c = getchar();
54
    if(c == '-')flag = -1, c = getchar();
55
    while(isdigit(c)){
56
        ret *= 10;
57
        ret += int(c - '0');
58
        c = getchar();
59
    }
60
    ret *= flag;
61
    return ret;
62
}

E - Bishop 2

题面

给定有障碍的网格图，. 为空地，# 为障碍。给定起点终点，每次移动仅可以斜向走任意长度，问从起点到终点的最少移动次数，可能无解，无解输出 -1。

Solution

BFS 较为显然，因为时限 6000ms，只要写的不太丑直接搜也能过。对于本题，使用 01BFS 较为显然。我们在宽搜每次搜一步且距离仅为 $1$$1$，并记录上一步的方向，如果同向则认为走了一个 $0$$0$ 边，异向则为 $1$$1$ 边，开个双端队列，同向插到前面，反之插到后面，按照正常宽搜每次取队头扩展即可。

需要注意对于 01BFS 时，我们判断是否走过和是否为答案的时候，需要在从队头取元素的时候判断，而不是在扩展的时候判断。因为如果在某一次由 $1$$1$ 扩展的时候如果直接把 $vis$$vis$ 设为 $\mathtt{\text{true}}$$\texttt{true}$，但是这可能会导致后面从 $0$$0$ 扩展的，本应能插在队列中比这个更前面的更优的无法转移，使答案更劣。同时我们也需要考虑到不同方向的时候扩展也是不同，所以 $vis$$vis$ 中也要考虑到方向这一维。

Code

xxxxxxxxxx
91
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 CHK(x, y) (x >= 1 && x <= N && y >= 1 && y <= N && !mp[x][y])
24

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

28
int N;
29
int dx[10] = {0,  -1, -1, 1, 1};
30
int dy[10] = {0,  -1, 1, -1, 1};
31
int vis[1600][1600][5];
32
bool mp[1600][1600];
33

34
struct Status{
35
    int x, y;
36
    int dir;//direction 1, 2, 3, 4
37
    int dist;
38
}S, T;
39
void Init(void){
40
    char c = getchar();
41
    for(int i = 1; i <= N; ++i)for(int j = 1; j <= N; ++j){
42
        while(c != '.' && c != '#')c = getchar();
43
        mp[i][j] = c == '.' ? false : true;
44
        c = getchar();
45
    }
46
}
47
void bfs(void){
48
    deque < Status > dq;
49
    dq.push_back(S);
50
    while(!dq.empty()){
51
        auto tp = dq.front(); dq.pop_front();
52
        if(vis[tp.x][tp.y][tp.dir])continue;
53
        vis[tp.x][tp.y][tp.dir] = true;
54
        if(tp.x == T.x && tp.y == T.y)
55
            printf("%d\n", tp.dist), exit(0);
56
        // printf("Current pos (%d, %d): dis = %d, dir = %d\n", tp.x, tp.y, tp.dist, tp.dir);
57
        for(int i = 1; i <= 4; ++i){
58
            int tx = tp.x + dx[i], ty = tp.y + dy[i];
59
            if(!CHK(tx, ty))continue;
60
            if(i == tp.dir)dq.push_front(Status{tx, ty, i, tp.dist});
61
            else dq.push_back(Status{tx, ty, i, tp.dist + 1});
62
        }
63
    }printf("-1\n");
64
}
65

66
int main(){
67
    // freopen("test_11.txt", "r", stdin);
68
    N = read();
69
    int x = read(), y = read(); S = Status{x, y, 0, 0};
70
    x = read(), y = read(); T = Status{x, y, 0, 0};
71
    Init();
72
    bfs();
73
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
74
    return 0;
75
}
76

77
template<typename T>
78
inline T read(void){
79
    T ret(0);
80
    short flag(1);
81
    char c = getchar();
82
    while(c != '-' && !isdigit(c))c = getchar();
83
    if(c == '-')flag = -1, c = getchar();
84
    while(isdigit(c)){
85
        ret *= 10;
86
        ret += int(c - '0');
87
        c = getchar();
88
    }
89
    ret *= flag;
90
    return ret;
91
}

F - typewriter

题面

给定 $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
86
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
        // cout << "tot_pre:" << bitset < 32 > (S) << endl;
62
        for(int i = 0; i <= N - 1; ++i)
63
            if((1 << i) & S)tot &= str[i + 1];
64
        // cout << "tot:" << bitset < 32 > (tot) << endl;
65
        ans = (ans + qpow(__builtin_popcount(tot), L) * ((cnt & 1) ? 1 : -1) + MOD) % MOD;
66
    }
67
    printf("%lld\n", ans);
68
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
69
    return 0;
70
}
71

72
template<typename T>
73
inline T read(void){
74
    T ret(0);
75
    short flag(1);
76
    char c = getchar();
77
    while(c != '-' && !isdigit(c))c = getchar();
78
    if(c == '-')flag = -1, c = getchar();
79
    while(isdigit(c)){
80
        ret *= 10;
81
        ret += int(c - '0');
82
        c = getchar();
83
    }
84
    ret *= flag;
85
    return ret;
86
}

G - Game on Tree 3

题面

类似于 LG-P3554 [POI2013]LUK-Triumphal arch，给定一棵树，有点权，B 初始在 $1$$1$，每轮 A 选择一个点将权值变为 $0$$0$，然后 B 移动一次，B 可在任意时刻停止游戏然后获得所在点上的权值的得分，两人均采取最优策略那么最终 B 最少会拿到多少的得分。

Solution

与 POI2013 基本相同，对于本题依然考虑二分答案，对于当前的答案 $k$$k$，认为大于 $k$$k$ 的贡献为 $1$$1$，小于等于的为 $0$$0$，于是显然有 dp，令 $dp(i)$$dp(i)$ 表示在 $i$$i$ 节点上时需要额外多少次的变为 $0$$0$ 的操作，显然有转移 $dp(i)=max(\sum _{j\in son(i)}dp(j)-1,0)+[v(i)>k]$$dp(i) = \max(\sum_{j \in son(i)} dp(j) - 1, 0) + \left[ v(i) \gt k \right]$，最后判断一下根节点 $1$$1$ 为 $0$$0$ 则合法，反之不合法。

Code

xxxxxxxxxx
89
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
template<typename T = int>
24
inline T read(void);
25

26
int N;
27
struct Edge{
28
    Edge* nxt;
29
    int to;
30
    OPNEW;
31
}ed[410000];
32
ROPNEW(ed);
33
Edge* head[210000];
34

35
int val[210000];
36
int mnval(INT_MAX), mxval(-1);
37
int f[210000];
38

39
void dfs(int k, int p = 1, int fa = 0){
40
    for(auto i = head[p]; i; i = i->nxt){
41
        if(SON == fa)continue;
42
        dfs(k, SON, p);
43
        f[p] += f[SON];
44
    }
45
    f[p] -= 1;
46
    f[p] = max(0, f[p]);
47
    f[p] += val[p] > k ? 1 : 0;
48
}
49
bool Check(int K){
50
    memset(f, 0, sizeof(f));
51
    dfs(K);
52
    return f[1] == 0;
53
}
54

55
int main(){
56
    N = read();
57
    for(int i = 2; i <= N; ++i)val[i] = read(), mxval = max(mxval, val[i]);
58
    for(int i = 1; i <= N - 1; ++i){
59
        int s = read(), t = read();
60
        head[s] = new Edge{head[s], t};
61
        head[t] = new Edge{head[t], s};
62
        if(s == 1)mnval = min(mnval, val[t]);
63
        if(t == 1)mnval = min(mnval, val[s]);
64
    }if(!head[1]->nxt)mnval = 0;
65
    int l = mnval, r = mxval;
66
    int ans(-1);
67
    while(l <= r){
68
        int mid = (l + r) >> 1;
69
        Check(mid) ? ans = mid, r = mid - 1 : l = mid + 1;
70
    }printf("%d\n", ans);
71
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
72
    return 0;
73
}
74

75
template<typename T>
76
inline T read(void){
77
    T ret(0);
78
    short flag(1);
79
    char c = getchar();
80
    while(c != '-' && !isdigit(c))c = getchar();
81
    if(c == '-')flag = -1, c = getchar();
82
    while(isdigit(c)){
83
        ret *= 10;
84
        ret += int(c - '0');
85
        c = getchar();
86
    }
87
    ret *= flag;
88
    return ret;
89
}

Ex - 01? Queries

题面

给定长度为 $N$$N$ 的仅包含 0，1，? 的字符串 $S$$S$，给定 $Q$$Q$ 组询问 $(x_1,c_1),(x_2,c_2),\cdots ,(x_q,c_q)$$(x_1, c_1), (x_2, c_2), \cdots, (x_q, c_q)$，每次将原字符串中 $x_i$$x_i$ 位置的字符改为 $c_i$$c_i$，然后输出 $S$$S$ 有多少种非空子串，? 需任意替换为 0 或 1。

Solution

太长了这里就直接放个链接吧。。

ABC246Ex 01? Queries Solution

Code

xxxxxxxxxx
117
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 MAXN (int)(1e5 + 100)
24
#define MOD (int)(998244353)
25

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

29
int N, Q;
30
int S[MAXN];
31

32
struct Matrix3{
33
    int val[3][3];
34
    Matrix3(int v00, int v01, int v02, int v10, int v11, int v12, int v20, int v21, int v22):
35
        val{
36
            {v00, v01, v02},
37
            {v10, v11, v12},
38
            {v20, v21, v22}
39
        }{;}
40
    Matrix3(int S):
41
        val{
42
            {1, S != 0, 0},
43
            {S != 1, 1, 0},
44
            {S != 1, S != 0, 1}
45
        }{;}
46
    Matrix3(int val[][3]){for(int i = 0; i <= 2; ++i)for(int j = 0; j <= 2; ++j)this->val[i][j] = val[i][j];}
47
    Matrix3(void) = default;
48
    friend const Matrix3 operator * (const Matrix3 &x, const Matrix3 &y){
49
        int val[3][3]; memset(val, 0, sizeof val);
50
        for(int i = 0; i <= 2; ++i)for(int j = 0; j <= 2; ++j)for(int p = 0; p <= 2; ++p)
51
            val[i][j] = ((ll)val[i][j] + (ll)x.val[i][p] * y.val[p][j] % MOD) % MOD;
52
        return Matrix3(val);
53
    }
54
    void Print(void){
55
        for(int i = 0; i <= 2; ++i)for(int j = 0; j <= 2; ++j)
56
            printf("%d%c", val[i][j], j == 2 ? '\n' : ' ');
57
    }
58
}mt[MAXN];
59

60
class SegTree{
61
private:
62
    Matrix3 tr[MAXN << 2];
63
    #define LS (p << 1)
64
    #define RS (LS | 1)
65
    #define MID ((gl + gr) >> 1)
66
public:
67
    void Pushup(int p){tr[p] = tr[LS] * tr[RS];}
68
    void Build(int p = 1, int gl = 1, int gr = N){
69
        if(gl == gr)return tr[p] = mt[gl = gr], void();
70
        Build(LS, gl, MID);
71
        Build(RS, MID + 1, gr);
72
        Pushup(p);
73
    }
74
    void Modify(int idx, Matrix3 v, int p = 1, int gl = 1, int gr = N){
75
        if(gl == gr)return tr[p] = v, void();
76
        if(idx <= MID)Modify(idx, v, LS, gl, MID);
77
        else Modify(idx, v, RS, MID + 1, gr);
78
        Pushup(p);
79
    }
80
    Matrix3 Query(void){return tr[1];}
81
}st;
82

83
int main(){
84
    N = read(), Q = read();
85
    string s; cin >> s;
86
    for(int i = 1; i <= (int)s.size(); ++i)
87
        S[i] = s.at(i - 1) == '?' ? -1 : int(s.at(i - 1) - '0'),
88
        mt[i] = Matrix3(S[i]);
89
    st.Build();
90
    Matrix3 origin(0, 0, 1, 0, 0, 0, 0, 0, 0);
91
    while(Q--){
92
        int p = read();
93
        char c = getchar(); while(c != '0' && c != '1' && c != '?')c = getchar();
94
        int flag = c == '?' ? -1 : int(c - '0');
95
        st.Modify(p, Matrix3(flag));
96
        auto ans = origin * st.Query();
97
        printf("%d\n", (int)((ll)(ans.val[0][0] + ans.val[0][1]) % MOD));
98
    }
99
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
100
    return 0;
101
}
102

103
template < typename T >
104
inline T read(void){
105
    T ret(0);
106
    short flag(1);
107
    char c = getchar();
108
    while(c != '-' && !isdigit(c))c = getchar();
109
    if(c == '-')flag = -1, c = getchar();
110
    while(isdigit(c)){
111
        ret *= 10;
112
        ret += int(c - '0');
113
        c = getchar();
114
    }
115
    ret *= flag;
116
    return ret;
117
}

UPD

update-2022_10_24 初稿