首页 模拟赛

# A. 数正方体

推了 2.5h 没有推出来，心态非常崩。

主要是没有网通项式方面去想，考场上推出来递推式之后一直在优化递推……

通过手模不难发现，fi,j=fi−1,j−1+2×fi−1,jf_{i, j} = f_{i - 1, j - 1} + 2 \times f_{i - 1, j}.

然后再打一个更大的表，不难发现

fn,m=2n−m(nm)f_{n, m} = 2^{n - m} \dbinom {n}{m}

然后 O(n)O(n) 预处理，O(1)O(1) 查询就好了。

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
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 1e5 + 10;
const int M = 1e4 + 10;
const int mod = 998244353;
int T, n, m;

inline int add(int x) {return x >= mod ? x - mod : x;}
inline int sub(int x) {return x < 0 ? x + mod : x;}
inline int mul(int x, int y) {return 1ll * x * y % mod;}

int fac[N], ifac[N];

inline int qpow(int a, int b){
    int res = 1;
    while(b){
        if(b & 1) res = mul(res, a);
        a = mul(a, a), b >>= 1;
    }
    return res;
}

inline void init(int n){
	fac[0] = 1;
	for(int i = 1; i <= n; ++i) fac[i] = mul(fac[i - 1], i);
	ifac[n] = qpow(fac[n], mod - 2);
	for(int i = n - 1; i >= 0; --i) ifac[i] = mul(ifac[i + 1], i + 1);
}

inline int C(int n, int m){
	return mul(fac[n], mul(ifac[m], ifac[n - m]));
}

inline void solve(){
	n = read(), m = read();
	write(mul(C(n, m), qpow(2, n - m))), puts("");
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    T = read(), init(N - 10);
    while(T--) solve();
    return 0;
}

# B. 数连通块

首先把题目中的树跑出来，设 pip_i 表示 ii 点存在的概率，qiq_i 表示 ii 点不存在的概率。

对于询问 l∼rl \sim r，考虑每个点对连通块个数的贡献。

设当前点为 xx，分类讨论：

  • faxfa_x 在 l∼rl \sim r 中，xx 想要对答案有贡献，那么必须 faxfa_x 不存在，且 xx 存在，所以贡献为 q[fax]×p[x]q[fa_x] \times p[x]。

  • faxfa_x 不在 l∼rl \sim r 中，只要 xx 存在就对答案就贡献，所以贡献为 p[x]p[x]。

暴力是 O(n2)O(n^2) 的，期望得分 10pts\text{10pts}，考虑使用莫队优化，然后就可以过了……

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>
#define pb push_back
#define be(x) x / B

using namespace std;

namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }

    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 1e5 + 10;
const int mod = 1e9 + 7;
int n, m, Q, B;
int p[N], q[N];
vector <int> g[N];

inline int add(int x, int y) {return x + y >= mod ? x + y - mod : x + y;}
inline int sub(int x) {return x < 0 ? x + mod : x;}
inline int mul(int x, int y) {return 1ll * x * y % mod;}

inline int qpow(int a, int b){
    int res = 1;
    while(b){
        if(b & 1) res = mul(res, a);
        a = mul(a, a), b >>= 1;
    }
    return res;
}

inline int inv(int a) {return qpow(a, mod - 2);}

int fa[N];

inline void dfs(int x, int f){
    fa[x] = f;
    for(auto y : g[x]) if(y != f) dfs(y, x);
}

struct node{
    int l, r, id;
    inline bool operator < (const node &b) const{
        return be(l) != be(b.l) ? l < b.l : r < b.r;
    }
}a[N];
int ans[N], s[N];
int l, r, res;

inline void add(int x){
    if(fa[x] >= l && fa[x] <= r) res = add(res, mul(p[x], q[fa[x]]));
    else res = add(res, p[x]);
    s[fa[x]] = add(s[fa[x]], p[x]), res = add(sub(res - s[x]), mul(s[x], q[x]));
}

inline void del(int x){
    if(fa[x] >= l && fa[x] <= r) res = sub(res - mul(p[x], q[fa[x]]));
    else res = sub(res - p[x]);
    s[fa[x]] = sub(s[fa[x]] - p[x]), res = add(sub(res - mul(s[x], q[x])), s[x]);
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = read(), m = read(), Q = read(), B = sqrt(n);
    for(int i = 1, a, b; i <= n; ++i)
        a = read(), b = read(), p[i] = mul(a, inv(b)), q[i] = sub(1 - p[i]);
    for(int i = 1; i <= m; ++i){
        int u = read(), v = read();
        g[u].pb(v), g[v].pb(u);
    }
    dfs(1, 0);
    for(int i = 1; i <= Q; ++i) a[i] = (node){read(), read(), i};
    sort(a + 1, a + 1 + Q);
    l = 1, r = 0;
    for(int i = 1; i <= Q; ++i){
        while(l > a[i].l) add(--l);
        while(r < a[i].r) add(++r);
        while(l < a[i].l) del(l++);
        while(r > a[i].r) del(r--);
        ans[a[i].id] = res;
    }
    for(int i = 1; i <= Q; ++i) write(ans[i]), puts("");
    return 0;
}

# C. 数大模拟

拿了暴力分跑路了 /kk

正解现在还不会，先咕了。

# D. 数字符串

暴力 Hash\text{Hash} 没什么好说的了，可以得 50pts\text{50pts}。

观察题目条件 2x≡i ( mod k)2x \equiv i\ (\bmod k)，我们开个桶记录合法的 2x2x 个数就好，fif_i 就可以直接算出来了。

考虑在失配树上跑，开个栈记录一条从上到下的链。因为是失配树，所以父亲是儿子的 border\text{border}，也就是满足条件②。

对于条件③，记录 pxp_x 表示 xx 到祖先的链上最远的合法的位置，具体怎么维护看代码吧。

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
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }

    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 1e6 + 10;
const int mod = 998244353;
char s[N];
int n, k, ans = 1;
int nxt[N];
vector <int> g[N];
int stk[N], top, buk[N], p[N], f[N];

inline void dfs(int x, int fa){
    if(x) stk[++top] = x, buk[2 * x % k]++;
    p[x] = p[fa];
    while(p[x] < top && 2 * stk[p[x] + 1] < x + 1) p[x]++, buk[2 * stk[p[x]] % k]--;
    f[x] = buk[x % k];
    for(auto y : g[x]) dfs(y, x);
    while(p[x] > p[fa]) buk[2 * stk[p[x]] % k]++, p[x]--;
    if(x) top--, buk[2 * x % k]--;
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    scanf("%s", s + 1), k = read();
    n = strlen(s + 1);
    for(int i = 2, j = 0; i <= n; ++i){
        while(j && s[i] != s[j + 1]) j = nxt[j];
        if(s[i] == s[j + 1]) j++;
        nxt[i] = j;
    }
    for(int i = 1; i <= n; ++i) g[nxt[i]].pb(i);
    dfs(0, 0);
    for(int i = 1; i <= n; ++i) ans = 1ll * ans * (f[i] + 1) % mod;
    write(ans), puts("");
    return 0;
}

更新于 阅读次数 次