AtCoder Beginner Contest 247 Solution

更好的阅读体验戳此进入

题面链接

题面 Luogu 链接

A - Move Right

题面

给定一个 $4$$4$ 位的二进制串，求其右移一位之后的值的二进制。

Solution

语法题没营养。

Code

xxxxxxxxxx
52
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
    printf("0");
28
    char c = getchar();
29
    for(int i = 1; i <= 4; ++i){
30
        while(c != '1' && c != '0')c = getchar();
31
        if(i !=  4)printf("%c", c);
32
        c = getchar();
33
    }printf("\n");
34
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
35
    return 0;
36
}
37

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

B - Unique Nicknames

题面

给定 $n$$n$ 个人的姓和名，定义一个人的昵称为他的姓或名，且一个人的昵称不能与其他人的姓或名重复，判断给定的数据是否能为每个人钦定一个昵称。可行输出 Yes，反之输出 No。

Solution

（语法题没一遍过，身败名裂了）

开个 map 维护一下每个字符串的出现次数，如果一个人的姓和名出现次数都大于等于 $2$$2$ 那么他的昵称无论选择姓还是名都会重复一定不合法。需要注意特判一下如果一个人的姓名相同那么就是出现次数大于等于 $3$$3$ 才会不合法。

Code

xxxxxxxxxx
57
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
unordered_map < string, int > name;
27
string fn[110], ln[110];
28

29
int main(){
30
    int N = read();
31
    for(int i = 1; i <= N; ++i){
32
        cin >> fn[i] >> ln[i];
33
        name[fn[i]]++, name[ln[i]]++;
34
    }
35
    for(int i = 1; i <= N; ++i)
36
        if((fn[i] == ln[i] && name[fn[i]] >= 3) || (fn[i] != ln[i] && name[fn[i]] >= 2 && name[ln[i]] >= 2))
37
            printf("No\n"), exit(0);
38
    printf("Yes\n");
39
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
40
    return 0;
41
}
42

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

C - 1 2 1 3 1 2 1

题面

我们按如下方式定义序列 $S_n$$S_n$：

$S_1$$S_1$ 只包含一个整数 $1$$1$。

$S_n$$S_n$ 为 $S_{n-1},n,S_{n-1}$$S_{n - 1}, n, S_{n - 1}$ 构成的序列。

给定 $n$$n$，输出序列 $S_n$$S_n$。

Solution

也算是个语法题吧。。

从定义就能看出来这是递归定义的，于是我们也写个递归，$n=1$$n = 1$ 的时候输出 $1$$1$，否则按照要求递归并输出即可。

（如果把 $n$$n$ 开大一点变成求第 $k$$k$ 位应该能略微增加一点难度）

Code

xxxxxxxxxx
55
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
void PrintAns(int n){
27
    if(n == 1)return printf("1 "), void();
28
    PrintAns(n - 1);
29
    printf("%d ", n);
30
    PrintAns(n - 1);
31
}
32

33
int main(){
34
    int N = read();
35
    PrintAns(N);
36
    printf("\n");
37
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
38
    return 0;
39
}
40

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

D - Cylinder

题面

存在一个队列，给定 $q$$q$ 个操作或询问，按以下格式输入：

1 x c，表示向队尾插入 $c$$c$ 个 $x$$x$。

2 c，表示从队头取出 $c$$c$ 个元素并输出它们的和。

Solution

大概也算是个语法题？

维护一个队列，里面元素是个 pair < int, int > 记录元素值和数量，$1$$1$ 操作就是队尾插入一个 {x, c}，$2$$2$ 操作判断一下，如果队头能取就取出来然后求和，否则对队头做一个类似 ODT 的 Split 的操作，然后对应维护一下 $ans$$ans$ 即可。

对于 $2$$2$ 操作详细解释一下，不难想到维护询问剩余的 $c$$c$，令队头元素的 $c$$c$ 为 $c^{\prime }$$c'$，值为 $x$$x$，显然若 $c^{\prime }\le c$$c' \le c$，那么直接 $c\leftarrow c-c^{\prime }$$c \leftarrow c - c'$ 然后答案加上 $c^{\prime }\times x$$c' \times x$ 后把队头弹出，反之答案加上 $c\times x$$c \times x$ 并 $c^{\prime }\leftarrow c^{\prime }-c$$c' \leftarrow c' - c$，注意判断队列非空即可。

Code

xxxxxxxxxx
64
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
queue < pair < int, int >/*value, cnt*/ > balls;
27

28
int main(){
29
    int N = read();
30
    while(N--){
31
        int opt = read();
32
        if(opt == 1){
33
            int x = read(), c = read();
34
            balls.push({x, c});
35
        }else{
36
            ll ans(0);
37
            int c = read();
38
            while(c > 0 && !balls.empty()){
39
                auto tp = balls.front();
40
                if(c >= tp.second)balls.pop(), c -= tp.second, ans += (ll)tp.first * tp.second;
41
                else ans += (ll)c * tp.first, balls.front().second -= c, c = 0;
42
            }printf("%lld\n", ans);
43
        }
44
    }
45

46
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
47
    return 0;
48
}
49

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

E - Max Min

题面

给定数列 $A_n$$A_n$，给定 $X,Y$$X, Y$，我们定义数对 $(L,R)$$(L, R)$ 满足 $1\le L\le R\le n$$1 \le L \le R \le n$，且数列 $A_L,A_{L+1},\cdots ,A_R$$A_L, A_{L + 1}, \cdots, A_R$ 满足最大值为 $X$$X$，最小值为 $Y$$Y$，求有多少种满足条件的数对。

Solution

关于本题有一些较为显然的 $O(n{\log }^{2}n)$$O(n \log ^2 n)$ 或 $O(n\log n)$$O(n \log n)$ 或 $O(n)$$O(n)$ 的做法，前两个大概对应着树套树和线段树，然后后者大概是维护前一个等于 $X$$X$ 等于 $Y$$Y$，在 $(X,Y)$$(X, Y)$ 之间的啊等等一堆东西然后跑一遍，这里就不多赘述了，网上相关做法很多。这里主要提供一个机房巨佬 @Zpair 想出来的人类智慧容斥的做法与推导。

首先我们考虑这段区间里一定不能包含在 $(-\mathrm{\infty },Y)\cup (X,+\mathrm{\infty })$$(-\infty, Y) \cup (X, +\infty)$ 内的数，所以我们考虑让所有在这个区间内的数作为分割点，这样最终会让我们的序列被分成很多个子序列，这里我们不难发现，合法的区间一定不会有跨越两个子区间的，一定都是在子区间内的子子区间。

所以这时候我们只需要对于每个划分出来的子区间考虑其中的合法区间即可，不难想到我们要找的区间合法当且仅当里面包含了至少一个 $X$$X$ 和至少一个 $Y$$Y$，为了方便记录这里我们令等于 $X$$X$ 的点为 $1$$1$，等于 $Y$$Y$ 的点为 $-1$$-1$，在 $(X,Y)$$(X, Y)$ 之间的点为 $0$$0$，也就是我们要找的就是每个子区间里包含 $-1$$-1$ 和 $1$$1$ 的区间由多少个。这里我们令包含 $1$$1$ 的区间的集合为 $A$$A$，包含 $-1$$-1$ 的为 $B$$B$，令子区间内的所有区间的集合为 $\mathrm{\Omega }$$\Omega$，不难想到我们比较好求的是，不包含 $1$$1$ 和 $-1$$-1$ 的区间，不包含 $1$$1$ 的区间，不包含 $-1$$-1$ 的区间，以及全集，分别对应着 $\bar{A}\cap \bar{B}$$\overline{A} \cap \overline{B}$，$\bar{A}$$\overline{A}$，$\bar{B}$$\overline{B}$，$\mathrm{\Omega }$$\Omega$。我们的目标是求出 $A\cap B$$A \cap B$，所以我们希望通过前面的四个求出答案，不难想到如下推导：

此时考虑如何维护这四个值，显然我们可以考虑把子区间再次进行分割，遍历三次，分别由 $1$$1$ 分割，由 $-1$$-1$ 分割，由 $-1$$-1$ 或 $1$$1$ 分割，也就分别对应着式子中的三个区间的大小，然后对于每个子区间维护一遍即可，最后就是一个大常数的线性求解。

然后还有个点就是如果 $X=Y$$X = Y$ 的话那么其实际上是既是 $1$$1$ 又是 $-1$$-1$，需要特判一下。

Code

xxxxxxxxxx
93
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, X, Y;
27
int a[210000];
28
int cnt0(0), cnt1(0), cnt_1(0), l(1), r(-1);
29
ll ans(0);
30

31
ll GetC(int n, int m){
32
    if(n == 1)return 1;
33
    if(!n || m > n)return 0;
34
    ll ret(1);
35
    for(int i = n; i >= n - m + 1; --i)ret *= i;
36
    for(int i = m; i >= 1; --i)ret /= i;
37
    return ret + n;
38
}
39

40
int main(){
41
    N = read(), X = read(), Y = read();
42
    for(int i = 1; i <= N + 1; ++i){
43
        a[i] = i <= N ? read() : INT_MAX;
44
        a[i] = a[i] == X && a[i] == Y ? -114514 : (a[i] == X ? 1 : (a[i] == Y ? -1 : (Y <= a[i] && a[i] <= X ? 0 : 114514)));
45
        if(a[i] != 114514){r = i; continue;}
46
        if(!~r){l = i + 1; continue;}
47
        ll cur(0);
48
        cur += GetC(r - l + 1, 2);
49
        int ll(l), rr(-1);
50
        for(int j = l; j <= r; ++j){
51
            if(a[j] != -1 && a[j] != -114514){rr = j; continue;}
52
            if(!~rr){ll = j + 1; continue;}
53
            cur -= GetC(rr - ll + 1, 2);
54
            ll = j + 1;
55
        }if(ll <= rr)cur -= GetC(rr - ll + 1, 2);
56
        ll = l, rr = -1;
57
        for(int j = l; j <= r; ++j){
58
            if(a[j] != 1 && a[j] != -114514){rr = j; continue;}
59
            if(!~rr){ll = j + 1; continue;}
60
            cur -= GetC(rr - ll + 1, 2);
61
            ll = j + 1;
62
        }if(ll <= rr)cur -= GetC(rr - ll + 1, 2);
63
        ll = l, rr = -1;
64
        for(int j = l; j <= r; ++j){
65
            if(!a[j]){rr = j; continue;}
66
            if(!~rr){ll = j + 1; continue;}
67
            cur += GetC(rr - ll + 1, 2);
68
            ll = j + 1;
69
        }if(ll <= rr)cur += GetC(rr - ll + 1, 2);
70
        ans += cur;
71
        l = i + 1;
72
    }
73
    printf("%lld\n", ans);
74

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
    short 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
}

然后因为我是完全按照这个思路实现的所以上面的可能非常丑，所以这里也贴一个 @Zpair 的优美实现。

xxxxxxxxxx
18
1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
int l1,l2,l3,l4,n,x,y;ll ans;
5
ll get(int x){return (ll)x*(x+1)/2;}
6
int main(){
7
    cin>>n>>x>>y;int v;
8
    for(int i=1;i<=n;++i){
9
        scanf("%d",&v);
10
        if(v>x||v<y){ans+=get(l1)-get(l2)-get(l3)+get(l4),l1=l2=l3=l4=0;continue;}
11
        if(v!=x&&v!=y)l1++,l2++,l3++,l4++;
12
        if(v==x&&v==y)l1++,ans+=-get(l2)-get(l3)+get(l4),l2=l3=l4=0;
13
        if(v==x&&v!=y)l1++,l3++,ans+=-get(l2)+get(l4),l2=l4=0;
14
        if(v!=x&&v==y)l1++,l2++,ans+=-get(l3)+get(l4),l3=l4=0;
15
    }
16
    ans+=get(l1)-get(l2)-get(l3)+get(l4);
17
    cout<<ans;
18
}

F - Cards

题面

给定 $n$$n$ 张卡片，每张卡片正反面各有一个数，给定每张卡片正面和反面的数，保证正面的数构成的序列，和反面的数构成的，分别均为 $1$$1$ 到 $n$$n$ 的排列，可以选择任意张卡片并获得其正反面的数，要求最终所有获得的数至少包含 $1$$1$ 到 $n$$n$ 每个数至少一次。求有多少种取法，对 $998244353$$998244353$ 取模。

Solution

考虑卡片之间的联系，显然若一个数在同一张卡牌的正反面那么这张卡牌必须选择，否则无法凑齐一个排列，反之这个数一定会在两张卡牌中出现，且这两张卡牌一定至少有一张被选择，否则依然无法凑齐一个排列，这个很好理解。

于是我们考虑一些对于这种题的一般的套路，可以尝试建图，对于本题不难想到，我们将一张卡牌作为一个点，将这个点向卡牌上存在的数的另一次出现所在的卡牌连一条边。抽象地说，对于一个数所在的两张（或一张）卡牌位置 $po{s}_{i,0}$$pos_{i, 0}$ 和 $po{s}_{i,1}$$pos_{i, 1}$，其中一定有一个刚好为 $i$$i$，我们就是要从 $i$$i$ 向不等于 $i$$i$ 的那个 $po{s}_i$$pos_i$ 连一条边，这里便不难想到从 $i$$i$ 向 $po{s}_{i,0}\oplus po{s}_{i,1}\oplus i$$pos_{i, 0} \oplus pos_{i, 1} \oplus i$ 连边即可。

不难想到这样会形成多个环，每一个环代表着其中几张卡牌，同时这些卡牌上的数在环内一定每个数都出现了两遍，如排列 $\{1,2,3\}$$\{ 1, 2, 3 \}$ 和排列 $\{2,1,3\}$$\{ 2, 1, 3 \}$，显然 $i=1$$i = 1$ 时向数字 $1$$1$ 所在的另一张卡牌 $2$$2$ 和数字 $2$$2$ 所在的另一张卡牌 $2$$2$ 连边（不拿发现很有可能存在重边与自环，所以需要注意判重并忽略），对于 $i=2$$i = 2$ 同理，最终一定会形成 $1\to 2\to 1$$1 \rightarrow 2 \rightarrow 1$ 和 $3\to 3$$3 \rightarrow 3$ 两个环，第一个环可以求出带有 $1,2$$1, 2$ 数字的卡牌的让 $1,2$$1, 2$ 都至少存在一次的卡牌选择方案数，第二个环则为 $3$$3$ 的方案数，将两者乘起来即为最终答案。并且环上每个边相连的两个点，或者说两张卡牌，至少要被选择一张，因为一条边连结的两个卡牌一定存在着相同的数，为了保证构成排列至少需要选择一个。

同时发现不同环的方案数，只跟环的长度有关，于是我们考虑令 $dp(i)$$dp(i)$ 表示 $i$$i$ 个数构成的环，则有边界 $dp(1)=1$$dp(1) = 1$ 和 $dp(2)=3$$dp(2) = 3$，和转移 $dp(i)=dp(i-1)+dp(i-2)$$dp(i) = dp(i - 1) + dp(i - 2)$，大概就是我们考虑向原环中插入第 $i$$i$ 个数，如果选择第 $i$$i$ 个数，那么任意的前 $i-1$$i - 1$ 个数的合法方案都可以接上新的这个数，反之如果不选第 $i$$i$ 个，那么第 $i$$i$ 个的两侧都应该是选择的，这个时候我们直观地可以想到，固定其左右的两个然后由 $dp(i-3)$$dp(i - 3)$ 转移而来，但是这个是有遗漏的。观察发现对于 $i$$i$ 不选择的，是存在类似 $\cdots \to 0\to 1\to i(0)\to 1\to 0\to \cdots$$\cdots \rightarrow 0 \rightarrow 1 \rightarrow i(0) \rightarrow 1 \rightarrow 0 \rightarrow \cdots$，也就是在固定三个之后左右各自接一个不选的，这个东西显然是不在 $dp(i-3)$$dp(i - 3)$ 里的，因为两个都不选接在一起形成环是不合法的，考虑如何正确地转移：我们可以考虑在 $dp(i-2)$$dp(i - 2)$ 的方案中找到任意一个选择的点，然后在其旁边接上 $i$$i$ 和另一个固定的选择的点，这样也是合法的且不重不漏，最终就是 $dp(i)=dp(i-1)+dp(i-2)$$dp(i) = dp(i - 1) + dp(i - 2)$。

于是考虑并查集维护好每个环的大小，$\prod dp(si{z}_i)$$\prod dp(siz_i)$ 即为最终的答案。

Code

xxxxxxxxxx
78
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;
29
int P[210000], Q[210000];
30
int cnt[210000];
31
int pos[210000][2];
32
int f[210000];
33
bool vis[210000];
34
int ans(1);
35

36
class UnionFind{
37
private:
38
public:
39
    int fa[210000];
40
    int siz[210000];
41
    UnionFind(void){for(int i = 1; i <= 201000; ++i)fa[i] = i, siz[i] = 1;}
42
    int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}
43
    void Union(int origin, int son){
44
        if(Find(origin) == Find(son))return;
45
        siz[Find(origin)] += siz[Find(son)], fa[Find(son)] = Find(origin);
46
    }
47
}uf;
48

49
int main(){
50
    N = read();
51
    f[1] = 1, f[2] = 3;
52
    for(int i = 3; i <= N; ++i)f[i] = (ll)(f[i - 1] + f[i - 2]) % MOD;
53
    for(int i = 1; i <= N; ++i)P[i] = read(), pos[P[i]][cnt[P[i]]++] = i;
54
    for(int i = 1; i <= N; ++i)Q[i] = read(), pos[Q[i]][cnt[Q[i]]++] = i;
55
    for(int i = 1; i <= N; ++i)
56
        uf.Union(i, pos[P[i]][0] ^ pos[P[i]][1] ^ i),
57
        uf.Union(i, pos[Q[i]][0] ^ pos[Q[i]][1] ^ i);
58
    for(int i = 1; i <= N; ++i)if(uf.Find(i) == i)ans = (ll)ans * f[uf.siz[uf.Find(i)]] % MOD;
59
    printf("%d\n", ans);
60
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
61
    return 0;
62
}
63

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

G - Dream Team

题面

咕咕咕

Solution

似乎是个费用流，先暂时咕掉了，以后再做。

Code

xxxxxxxxxx
1
1
//TODO

Ex - Rearranging Problem

题面

分治NTT，跳！

Solution

等联赛考完如果考过了再来做吧。。

Code

xxxxxxxxxx
1
1
//TODO

UPD

update-2022_10_25 初稿