依然 abcd 太水了所以跳了

[ABC253E] Distance Sequence

题面

$n, m, k$ $a_n$ ，满足：

$1 \le a_i \le m (1 \le i \le m)$ 。
$\lvert a_i - a_{i + 1} \rvert \ge k (1 \le i \le n - 1)$ 。

Solution

$dp(i, j)$ $i$ $j$ $\texttt{2D1D}$ 的转移，即：

d p (i, j) = \sum_{k = j + k}^{m} d p (i - 1, k) + \sum_{k = 1}^{j - k} d p (i - 1, k)

$j + k \le m$ $j - k \ge 1$ $\texttt{2D0D}$ $O(nm)$ 的。然后滚动数组也可以压掉一维，不过没必要，空间开的下。

$k = 0$ $dp(i - 1, j)$ $dp(i - 1, j)$ 。

Code


xxxxxxxxxx
61
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(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

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

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
#define MOD (ll)(998244353ll)
23

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

27
int N, M, K;
28
ll dp[1100][5100];
29
ll sum[5100];
30

31
int main(){
32
    N = read(), M = read(), K = read();
33
    for(int i = 1; i <= M; ++i)dp[1][i] = 1, sum[i] = i;
34
    for(int i = 2; i <= N; ++i){
35
        for(int j = 1; j <= M; ++j){
36
            (dp[i][j] += j + K <= M ? (sum[M] - sum[j + K - 1] + MOD) % MOD : 0) %= MOD;
37
            (dp[i][j] += j - K >= 1 ? sum[j - K] : 0) %= MOD;
38
            if(!K)(dp[i][j] += -(sum[j] - sum[j - 1]) + MOD) %= MOD;
39
        }
40
        for(int j = 1; j <= M; ++j)
41
            sum[j] = (sum[j - 1] + dp[i][j]) % MOD;
42
    }printf("%lld\n", sum[M]);
43
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
44
    return 0;
45
}
46

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

[ABC253F] Operations on a Matrix

题面

$n$ $m$ $q$ $3$ 种格式。

1 l r x $[l, r]$ $x$ 。
2 i x $i$ $x$ 。
3 i j $(i, j)$ 位置的元素值。

Solution

感觉还算是一道细节不少的题。

首先这道题的做法不少，主流的就是类似二位偏序维护，或者写一个区间修改的主席树。

这里主要说一下用 BIT 维护的方法。

$2$ $1$ $1$ $2$ $r$ $x$ $y$ $x$ $l$ $[l, r]$ $y$ 列的操作。

思路就是这样，维护的方式还是有些高妙的。先考虑离线一遍，然后维护对于每个查询的上一次对应的推平，同时维护该查询的初始值，然后在需要减去的位置开个 basic_string 插进去需要减的序号。然后我们考虑会有一次区间的查询，用 BIT 和前缀和维护，再遍历一次操作，先将前缀加起来，然后减去的那个前缀就在我们第二次遍历的时候通过遍历对应的 basic_string 而减去。然后最后跑一遍输出答案即可。

Code


xxxxxxxxxx
93
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(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

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

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

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

25
int N, M, Q;
26
int lst[210000], pos[210000];
27
ll ans[210000];
28
struct Query{int opt; int a, b, c;}qs[210000];
29
basic_string < int > del[210000];
30

31
class BIT{
32
private:
33
    ll tr[210000];
34
public:
35
    int lowbit(int x){return x & -x;}
36
    void Modify(int x, int v){while(x <= M)tr[x] += v, x += lowbit(x);}
37
    ll Query(int x){ll ret(0); while(x)ret += tr[x], x -= lowbit(x); return ret;}
38
    void ModifyRange(int l, int r, ll v){Modify(l, v), Modify(r + 1, -v);}
39
}bit;
40

41
int main(){
42
    // freopen("test_05.txt", "r", stdin);
43
    // freopen("out.txt", "w", stdout);
44
    N = read(), M = read(), Q = read();
45
    for(int i = 1; i <= Q; ++i){
46
        int opt = read();
47
        switch(opt){
48
            case 1:{
49
                int l = read(), r = read(), v = read(); qs[i] = Query{opt, l, r, v};
50
                break;
51
            }
52
            case 2:{
53
                int p = read(), v = read(); qs[i] = Query{opt, p, v};
54
                pos[p] = i;
55
                break;
56
            }
57
            case 3:{
58
                int x = read(), y = read(); qs[i] = Query{opt, x, y};
59
                ans[i] = qs[pos[x]].b;
60
                del[pos[x]] += i;
61
                break;
62
            }
63
            default: break;
64
        }
65
    }
66
    for(int i = 1; i <= Q; ++i){
67
        switch(qs[i].opt){
68
            case 1:{bit.ModifyRange(qs[i].a, qs[i].b, qs[i].c); break;}
69
            case 2:{for(auto p : del[i])ans[p] -= bit.Query(qs[p].b); break;}
70
            case 3:{ans[i] += bit.Query(qs[i].b); break;}
71
            default: break;
72
        }
73
    }
74
    for(int i = 1; i <= Q; ++i)if(qs[i].opt == 3)printf("%lld\n", ans[i]);
75
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
76
    return 0;
77
}
78

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

[ABC253G] Swap Many Times

题面

$n$ $a$ $i(1\le i\le n)$ $a_i=i$ 。

$n$ $\frac{n(n-1)}{2}$ $1\le l<r\le n$ $(l,r)$ $l$ $r$ 为第二关键字由小到大排序。

$n=4$ ，时，二元组序列为：

$(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)$

$(l,r)$ $a_l$ $a_r$ 。

$L$ $R$ $L$ $R$ 个二元组所对应的操作后的序列。

Solution

$l$ $l$ $l$ $siz$ 位，思路和性质都很简单，但是实现起来就特别恶心了，需要考虑大量细节。

Code


xxxxxxxxxx
79
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(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

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

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

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

25
int N;
26
ll L, R;
27
ll spl[210000];
28
int a[210000];
29
int ans[210000];
30

31
int main(){
32
    N = read(), L = read < ll >(), R = read < ll >();
33
    for(int i = 1; i <= N; ++i)a[i] = i;
34
    for(int i = 1; i <= N; ++i)spl[i] = spl[i - 1] + N - i;
35
    int lp = distance(spl, lower_bound(spl + 1, spl + N + 1, L));
36
    int rp = distance(spl, upper_bound(spl + 1, spl + N + 1, R));
37
    if(lp == rp){
38
        for(ll cur = L; cur <= R; ++cur){
39
            int pos = cur - spl[lp - 1];
40
            swap(a[lp], a[lp + pos]);
41
        }
42
        for(int i = 1; i <= N; ++i)printf("%d%c", a[i], i == N ? '\n' : ' ');
43
        exit(0);
44
    }
45
    for(ll cur = L; cur <= spl[lp]; ++cur){
46
        int pos = cur - spl[lp - 1];
47
        swap(a[lp], a[lp + pos]);
48
    }
49
    for(int i = 1; i <= lp; ++i)ans[i] = a[i];
50
    if(lp + 1 < rp){
51
        int s = lp + 1, siz = rp - lp - 1;
52
        for(int cnt = 0; s + siz + cnt <= N; ++cnt)ans[s + siz + cnt] = a[s + cnt];
53
        for(int cnt = 0; cnt <= siz - 1; ++cnt)ans[s + cnt] = a[N - cnt];
54
    }else
55
        for(int i = 1; i <= N; ++i)ans[i] = a[i];
56
    for(ll cur = spl[rp - 1] + 1; cur <= R; ++cur){
57
        int pos = cur - spl[rp - 1];
58
        swap(ans[rp], ans[rp + pos]);
59
    }
60
    for(int i = 1; i <= N; ++i)printf("%d%c", ans[i], i == N ? '\n' : ' ');
61
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
62
    return 0;
63
}
64

65
template < typename T >
66
inline T read(void){
67
    T ret(0);
68
    int flag(1);
69
    char c = getchar();
70
    while(c != '-' && !isdigit(c))c = getchar();
71
    if(c == '-')flag = -1, c = getchar();
72
    while(isdigit(c)){
73
        ret *= 10;
74
        ret += int(c - '0');
75
        c = getchar();
76
    }
77
    ret *= flag;
78
    return ret;
79
}

[ABC253Ex] We Love Forest

题面

$n$ $m$ $m$ $n - 1$ $1, 2, \cdots, n - 1$ $998244353$ 取模。

Solution

考虑 FZT，即子集计数，具体可参考 FZT - 子集计数学习笔记或 [ABC213G] Connectivity 2 Solution，发现本题与 ABC213G 相似。

因为本题存在选的边数的限制，所以不难想到需要在一般 FZT 的状态中额外添加一维记录。

$F(i, S)$ $i$ $S$ $G(S)$ $S$ 生成树的总方案数。

$G(S)$ $cnt(S, T)$ $S$ $T$ 之间的边数，方程不难想到为：

G (S) = \sum_{T ⊊ S} G (T) \times G (S \oplus T) \times c n t (T, S \oplus T)

$T$ $S \oplus T$ $\dfrac{1}{2}$ $\dfrac{1}{\lvert S \rvert - 1}$ ，故可以考虑将转移改为：

G (S) = \frac{1}{2 (| S | - 1)} \sum_{T ⊊ S} G (T) \times G (S \oplus T) \times c n t (T, S \oplus T)

或：

G (S) = \frac{1}{| S | - 1} \sum_{lowbit (S) \in T ⊊ S} G (T) \times G (S \oplus T) \times c n t (T, S \oplus T)

$G(2^k) = 1$ 。

$cnt$ $O(2^{2n}m)$ $cnte(S)$ $S$ $cnt$ 可以如下容斥：

c n t (S, T) = c n t e (S \lor T) - c n t e (S) - c n t e (T)

$cnte$ $O(m2^n)$ $cnt$ $O(1)$ $G$ $O(3^n)$ 的。

$L$ $\det(L_0)$ $L_0$ $L$ $i$ $i$ $i$ 任意。具体证明参考矩阵树定理（Matrix-tree Theorem）笔记。所以只需要矩阵建出来无脑求一下行列式即可。

$F$ $\lvert S \rvert$ $S$ 中点的数量，也就是 __builtin_popcount(S)，不难发现转移：

F (i, S) = \sum_{1 \in T ⊊ S} G (T) \times F (i - (| T | - 1), S \oplus T)

$1$ 节点在树中可以去重，具体在 ABC213G 也有说明。

$1$ $1$ $S$ $1$ $\operatorname{lowbit}(S)$ $S \land -S$ 。于是转移改为：

F (i, S) = \sum_{lowbit (S) \in T ⊊ S} G (T) \times F (i - (| T | - 1), S \oplus T)

$S$ $i + 1$ $F(i, S) = G(S)$ 。

$Smx = 2^n - 1$ $i$ $ans_i$ 有：

a n s_{i} = \frac{F (i, S m x) \times i!}{m^{i}} mod 998244353

$m_i$ $i$ $i!$ 。

$G$ $O(n^3 2^n)$ $F$ $O(n 3^n)$ $O((m + n^3) 2^n + 3^n)$ ，可以通过。

Code


xxxxxxxxxx
105
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(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

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

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
#define MAX_STATUS (20000)
23
#define MOD (ll)(998244353)
24
#define EXIST(x) (S & (1 << ((x) - 1)))
25

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

29
struct Edge{
30
    Edge* nxt;
31
    int to;
32
    OPNEW;
33
}ed[1100];
34
ROPNEW(ed);
35
Edge* head[20];
36

37
int N, M;
38
int deg[20];
39
ll G[MAX_STATUS], F[20][MAX_STATUS];
40
int cnte[MAX_STATUS];
41
ll fact[30];
42

43
int lowbit(int x){return x & -x;}
44
int CalCnt(int S, int T){return cnte[S | T] - cnte[S] - cnte[T];}
45
ll qpow(ll a, ll b){
46
    ll ret(1), mul(a);
47
    while(b){
48
        if(b & 1)ret = ret * mul % MOD;
49
        b >>= 1;
50
        mul = mul * mul % MOD;
51
    }return ret;
52
}
53

54
int main(){fact[0] = 1;
55
    for(int i = 1; i <= 20; ++i)fact[i] = fact[i - 1] * i % MOD;
56
    N = read(), M = read();
57
    const int Smx = (1 << N) - 1;
58
    for(int i = 1; i <= M; ++i){
59
        int s = read(), t = read();
60
        head[s] = new Edge{head[s], t};
61
        head[t] = new Edge{head[t], s};
62
    }
63
    for(int S = Smx; S; S = (S - 1) & Smx){
64
        int cnt(0);
65
        for(int p = 1; p <= N; ++p)
66
            for(auto i = head[p]; i; i = i->nxt)
67
                if(EXIST(p) && EXIST(SON))++cnt;
68
        cnt >>= 1;
69
        cnte[S] = cnt;
70
    }
71
    for(int S = 1; S <= Smx; ++S){
72
        if(__builtin_popcount(S) == 1){G[S] = 1; continue;}
73
        for(int T = (S - 1) & S; T; T = (T - 1) & S)
74
            if(T & lowbit(S))
75
                (G[S] += G[T] * G[S ^ T] % MOD * CalCnt(T, S ^ T) % MOD) %= MOD;
76
        (G[S] *= qpow(__builtin_popcount(S) - 1, MOD - 2)) %= MOD;
77
    }
78
    for(int i = 0; i <= N - 1; ++i)
79
        for(int S = 0; S <= Smx; ++S){
80
            if(__builtin_popcount(S) == i + 1){F[i][S] = G[S]; continue;}
81
            for(int T = (S - 1) & S; T; T = (T - 1) & S)
82
                if(T & lowbit(S) && i - (__builtin_popcount(T) - 1) >= 0)
83
                    (F[i][S] += G[T] * F[i - (__builtin_popcount(T) - 1)][S ^ T]) %= MOD;
84
        }
85
    for(int i = 1; i <= N - 1; ++i)
86
        printf("%lld\n", F[i][Smx] * fact[i] % MOD * qpow(qpow(M, i), MOD - 2) % MOD);
87
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
88
    return 0;
89
}
90

91
template < typename T >
92
inline T read(void){
93
    T ret(0);
94
    int flag(1);
95
    char c = getchar();
96
    while(c != '-' && !isdigit(c))c = getchar();
97
    if(c == '-')flag = -1, c = getchar();
98
    while(isdigit(c)){
99
        ret *= 10;
100
        ret += int(c - '0');
101
        c = getchar();
102
    }
103
    ret *= flag;
104
    return ret;
105
}

UPD

update-2022_12_07 初稿

AtCoder Beginner Contest 253 Solution

更好的阅读体验戳此进入

题面链接

题面 Luogu 链接

依然 abcd 太水了所以跳了

[ABC253E] Distance Sequence

题面

Solution

Code

[ABC253F] Operations on a Matrix

题面

Solution

Code

[ABC253G] Swap Many Times

题面

Solution

Code

[ABC253Ex] We Love Forest

题面

Solution

Code

UPD