**蒟蒻来讲题，还望大家喜。若哪有问题，大家尽可提！

Hello, 大家好哇！本初中生蒟蒻讲解一下AtCoder Beginner Contest 293这场比赛的A-E题！

===========================================================================================

A - Swap Odd and Even

原题

Problem Statement

You are given a string SSS of even length consisting of lowercase English letters. Let ∣S∣|S|∣S∣ be the length of SSS, and SiS_iSi​ be the iii-th character of SSS.
Perform the following operation for each i=1,2,…,∣S∣2i = 1, 2, \ldots, \frac{|S|}{2}i=1,2,…,2∣S∣​ in this order, and print the final SSS.
Swap S2i−1S_{2i-1}S2i−1​ and S2iS_{2i}S2i​.

Constraints

SSS is a string of even length consisting of lowercase English letters.
The length of SSS is at most 100100100.

Input

The input is given from Standard Input in the following format:
SSS

Output

Print the answer.

Sample Input 1

abcdef

Sample Output 1

badcfe
Initially, S=S =S= abcdef.

Performing the operation for i=1i = 1i=1 swaps S1S_1S1​ and S2S_2S2​, making S=S =S= bacdef.

Performing the operation for i=2i = 2i=2 swaps S3S_3S3​ and S4S_4S4​, making S=S =S= badcef.

Performing the operation for i=3i = 3i=3 swaps S5S_5S5​ and S6S_6S6​, making S=S =S= badcfe.

Thus, badcfe should be printed.

Sample Input 2

aaaa

Sample Output 2

aaaa

Sample Input 3

atcoderbeginnercontest

Sample Output 3

taocedbrgeniencrnoetts

题目大意

本题就是给出一个字符串，交换S2i−1S_{2i-1}S2i−1​ 和 S2iS_{2i}S2i​（ i=1,2,…,∣S∣2i = 1, 2, \ldots, \frac{|S|}{2}i=1,2,…,2∣S∣​）

思路

用swap交换一下就行，过于简单，不再多说~~~

代码

#include 
#define endl '\n'
#define pb(i) push_back(i)using namespace std;inline int read()
{int w = 1, s = 0;char c = getchar();while (c < '0' || c > '9'){if (c == '-') w = -1;c = getchar();}while (c >= '0' && c <= '9') s = s * 10 + c - '0', c = getchar();return w * s;
}int main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);string s;cin >> s;s = ' ' + s;for (int i = 1; i <= (int)s.size() / 2; i ++)swap(s[2 * i - 1], s[2 * i]);s.erase(0, 1);cout << s << endl;return 0;
}

B - Call the ID Number

原题

Problem Statement

There are NNN people whose IDs are 111, 222, …\ldots…, and NNN.
Each of person 111, person 222, …\ldots…, and person NNN performs the following action once in this order:
If person iii’s ID has not been called out yet, call out person AiA_iAi​’s ID.
Enumerate the IDs of all the people whose IDs are never called out until the end in ascending order.

Constraints

2≤N≤2×1052 \leq N \leq 2 \times 10^52≤N≤2×105
1≤Ai≤N1 \leq A_i \leq N1≤Ai​≤N
Ai≠iA_i \neq iAi​=i
All values in the input are integers.

Input

The input is given from Standard Input in the following format:
NNN
A1A_1A1​ A2A_2A2​ …\ldots… ANA_NAN​

Output

Enumerate the IDs of all the people whose IDs are not called out until the end in ascending order in the following format:
KKK
X1X_1X1​ X2X_2X2​ …\ldots… XKX_KXK​
In other words, the first line should contain the number of people, KKK, whose IDs are never called out until the end;
the second line should contain the sequence (X1,X2,…,XK)(X_1, X_2, \ldots, X_K)(X1​,X2​,…,XK​) of IDs of such people in ascending order, with spaces in between.

Sample Input 1

5
3 1 4 5 4

Sample Output 1

2
2 4
The five people’s actions are as follows.
Person 111’s ID has not been called out yet, so person 111 calls out person 333’s ID.
Person 222’s ID has not been called out yet, so person 222 calls out person 111’s ID.
Person 333’s ID has already been called out by person 111, so nothing happens.
Person 444’s ID has not been called out yet, so person 444 calls out person 555’s ID.
Person 555’s ID has already been called out by person 444, so nothing happens.
Therefore, person 222 and 444’s IDs are not called out until the end.

Sample Input 2

20
9 7 19 7 10 4 13 9 4 8 10 15 16 3 18 19 12 13 2 12

Sample Output 2

10
1 2 5 6 8 11 14 17 18 20

题目大意

本题就是对于每一个人（当他没有叫走时）他可以叫走第AiA_iAi​个人，最后问你有多少个人没被叫走，并输出编号

思路

直接暴力一遍即可

代码

#include 
#include 
#define endl '\n'
#define pb(i) push_back(i)using namespace std;const int N = 2e5 + 10;int n;
bool st[N];
int a[N];inline int read()
{int w = 1, s = 0;char c = getchar();while (c < '0' || c > '9'){if (c == '-') w = -1;c = getchar();}while (c >= '0' && c <= '9') s = s * 10 + c - '0', c = getchar();return w * s;
}int main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);cin >> n;for (int i = 1; i <= n; i ++)cin >> a[i];for (int i = 1; i <= n; i ++)if (!st[i])st[a[i]] = 1;int res = 0;vector ans;for (int i = 1; i <= n; i ++)if (st[i] == 0){res ++;ans.pb(i);}cout << res << endl;for (auto c :ans)cout << c << " ";return 0;
}

C - Make Takahashi Happy

原题

Problem Statement

There is a grid with HHH horizontal rows and WWW vertical columns.
For two integers iii and jjj such that 1≤i≤H1 \leq i \leq H1≤i≤H and 1≤j≤W1 \leq j \leq W1≤j≤W,
the square at the iii-th row from the top and jjj-th column from the left (which we denote by (i,j)(i, j)(i,j)) has an integer Ai,jA_{i, j}Ai,j​ written on it.
Takahashi is currently at (1,1)(1,1)(1,1).
From now on, he repeats moving to an adjacent square to the right of or below his current square until he reaches (H,W)(H, W)(H,W).
When he makes a move, he is not allowed to go outside the grid.
Takahashi will be happy if the integers written on the squares he visits (including initial (1,1)(1, 1)(1,1) and final (H,W)(H, W)(H,W)) are distinct.
Find the number of his possible paths that make him happy.

Constraints

2≤H,W≤102 \leq H, W \leq 102≤H,W≤10
1≤Ai,j≤1091 \leq A_{i, j} \leq 10^91≤Ai,j​≤109
All values in the input are integers.

Input

The input is given from Standard Input in the following format:
HHH WWW
A1,1A_{1, 1}A1,1​ A1,2A_{1, 2}A1,2​ …\ldots… A1,WA_{1, W}A1,W​
A2,1A_{2, 1}A2,1​ A2,2A_{2, 2}A2,2​ …\ldots… A2,WA_{2, W}A2,W​
⋮\vdots⋮
AH,1A_{H, 1}AH,1​ AH,2A_{H, 2}AH,2​ …\ldots… AH,WA_{H, W}AH,W​

Output

Print the answer.

Sample Input 1

3 3
3 2 2
2 1 3
1 5 4

Sample Output 1

3
There are six possible paths:
(1,1)→(1,2)→(1,3)→(2,3)→(3,3)(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3)(1,1)→(1,2)→(1,3)→(2,3)→(3,3): the integers written on the squares he visits are 3,2,2,3,43, 2, 2, 3, 43,2,2,3,4, so he will not be happy.
(1,1)→(1,2)→(2,2)→(2,3)→(3,3)(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)(1,1)→(1,2)→(2,2)→(2,3)→(3,3): the integers written on the squares he visits are 3,2,1,3,43, 2, 1, 3, 43,2,1,3,4, so he will not be happy.
(1,1)→(1,2)→(2,2)→(3,2)→(3,3)(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3)(1,1)→(1,2)→(2,2)→(3,2)→(3,3): the integers written on the squares he visits are 3,2,1,5,43, 2, 1, 5, 43,2,1,5,4, so he will be happy.
(1,1)→(2,1)→(2,2)→(2,3)→(3,3)(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)(1,1)→(2,1)→(2,2)→(2,3)→(3,3): the integers written on the squares he visits are 3,2,1,3,43, 2, 1, 3, 43,2,1,3,4, so he will not be happy.
(1,1)→(2,1)→(2,2)→(3,2)→(3,3)(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3)(1,1)→(2,1)→(2,2)→(3,2)→(3,3): the integers written on the squares he visits are 3,2,1,5,43, 2, 1, 5, 43,2,1,5,4, so he will be happy.
(1,1)→(2,1)→(3,1)→(3,2)→(3,3)(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3)(1,1)→(2,1)→(3,1)→(3,2)→(3,3): the integers written on the squares he visits are 3,2,1,5,43, 2, 1, 5, 43,2,1,5,4, so he will be happy.
Thus, the third, fifth, and sixth paths described above make him happy.

Sample Input 2

10 10
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 99 100

Sample Output 2

48620
In this example, every possible path makes him happy.

题目大意

本题就是从左上角走到右下角，途中不经过相同数字的点的个数，问有多少种满足条件的路径！

思路

这道题我么可以直接用DFS深搜一遍即可，相信大家都会DFS了所以就不过多赘述（有不会的，可以私聊我！）

代码

#include 
#include 
#define endl '\n'
#define pb(i) push_back(i)using namespace std;const int N = 2e1 + 10;int n, m;
int a[N][N];
unordered_map st;
int dx[2] = {1, 0}, dy[2] = {0, 1};
int res = 0;inline int read()
{int w = 1, s = 0;char c = getchar();while (c < '0' || c > '9'){if (c == '-') w = -1;c = getchar();}while (c >= '0' && c <= '9') s = s * 10 + c - '0', c = getchar();return w * s;
}void dfs(int x, int y)
{if (x == n && y == m){res ++;return;}for (int i = 0; i < 2; i ++){int xx = x + dx[i], yy = y + dy[i];if (xx < 1 || yy < 1 || xx > n || yy > m || st[a[xx][yy]]) continue;st[a[xx][yy]] = 1;dfs(xx, yy);st[a[xx][yy]] = 0;}
}int main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);cin >> n >> m;for (int i = 1; i <= n; i ++)for (int j = 1; j <= m; j ++)cin >> a[i][j];st[a[1][1]] = 1;dfs(1, 1);cout << res << endl;return 0;
}

D - Tying Rope（毒瘤！！！）

原题

Problem Statement

There are NNN ropes numbered 111 through NNN. One end of each rope is painted red, and the other is painted blue.
You are going to perform MMM operations of tying ropes. In the iii-th operation, you tie the end of rope AiA_iAi​ painted BiB_iBi​ with the end of rope CiC_iCi​ painted DiD_iDi​, where R means red and B means blue. For each rope, an end with the same color is not tied multiple times.
Find the number of groups of connected ropes that form cycles, and the number of those that do not, after all the operations.
Here, a group of connected ropes {v0,v1,…,vx−1}\lbrace v_0, v_1, \ldots, v_{x-1} \rbrace{v0​,v1​,…,vx−1​} is said to form a cycle if one can rearrange the elements of vvv so that, for each KaTeX parse error: Expected 'EOF', got '&' at position 10: 0 \leq i &̲lt; x, rope viv_ivi​ is tied to rope v(i+1)modxv_{(i+1) \bmod x}v(i+1)modx​.

Constraints

1≤N≤2×1051 \leq N \leq 2 \times 10^51≤N≤2×105
0≤M≤2×1050 \leq M \leq 2 \times 10^50≤M≤2×105
1≤Ai,Ci≤N1 \leq A_i, C_i \leq N1≤Ai​,Ci​≤N
(Ai,Bi)≠(Aj,Bj),(Ci,Di)≠(Cj,Dj)(A_i, B_i) \neq (A_j, B_j), (C_i, D_i) \neq (C_j, D_j)(Ai​,Bi​)=(Aj​,Bj​),(Ci​,Di​)=(Cj​,Dj​) (i≠j)(i \neq j)(i=j)
(Ai,Bi)≠(Cj,Dj)(A_i, B_i) \neq (C_j, D_j)(Ai​,Bi​)=(Cj​,Dj​)
N,M,AiN, M, A_iN,M,Ai​, and CiC_iCi​ are integers.
BiB_iBi​ is R or B, and so is DiD_iDi​.

Input

The input is given from Standard Input in the following format:
NNN MMM
A1A_1A1​ B1B_1B1​ C1C_1C1​ D1D_1D1​
A2A_2A2​ B2B_2B2​ C2C_2C2​ D2D_2D2​
⋮\vdots⋮
AMA_MAM​ BMB_MBM​ CMC_MCM​ DMD_MDM​

Output

Print XXX and YYY in this order, separated by a space, where XXX is the number of groups of connected ropes that form cycles, and YYY is the number of those that do not.

Sample Input 1

5 3
3 R 5 B
5 R 3 B
4 R 2 B

Sample Output 1

1 2
There are three groups of connected ropes: {1}\lbrace 1 \rbrace{1}, {2,4}\lbrace 2,4 \rbrace{2,4}, and {3,5}\lbrace 3,5 \rbrace{3,5}.
The group of ropes {3,5}\lbrace 3,5 \rbrace{3,5} forms a cycle, while the groups of rope {1}\lbrace 1 \rbrace{1} and ropes {2,4}\lbrace 2,4 \rbrace{2,4} do not. Thus, X=1X = 1X=1 and Y=2Y = 2Y=2.

Sample Input 2

7 0

Sample Output 2

0 7

Sample Input 3

7 6
5 R 3 R
7 R 4 R
4 B 1 R
2 R 3 B
2 B 5 B
1 B 7 B

Sample Output 3

2 1

题目大意

这题太恶心了！跟颜色压根没关系！这道题就是将绳子AiA_iAi​和CiC_iCi​连在一起，最后判断有多少个连通块是环，有多少个不是环！

思路

首先刚才也说了跟颜色没关系，所以我们就大胆的判断有多少个换就行了（不会可以看判断图中存在闭环的常用方法，本题我用的并查集的方法，并查集只限于无向图），那不是换的怎么算呢？我们可以用到Flood Fill算法计算有多少个连通块，再用连通块的数量减去有环的连通块的数量即为非环的数量！

代码

#include 
#include 
#define endl '\n'
#define pb(i) push_back(i)using namespace std;const int N = 2e5 + 10;int p[N];
int st[N];
bool flg;
vector g[N];inline int read()
{int w = 1, s = 0;char c = getchar();while (c < '0' || c > '9'){if (c == '-') w = -1;c = getchar();}while (c >= '0' && c <= '9') s = s * 10 + c - '0', c = getchar();return w * s;
}int find(int x)
{if (p[x] != x) p[x] = find(p[x]);return p[x];
}void dfs(int u)
{	st[u] = 1;for (auto c : g[u])if (!st[c])dfs(c);
}int main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int n, m;cin >> n >> m;for (int i = 1; i <= n; i ++)p[i] = i;int u, q, x = 0, y =0 ;char gun1, gun2;for (int i = 1; i <= m; i ++){cin >> u >> gun1 >> q >> gun2;//建边g[u].pb(q);g[q].pb(u);if (find(u) == find(q)) //有环了！x ++;else p[find(u)] = find(q); //合并集合}//计算连通块的数量int res = 0;for (int i = 1; i <= n; i ++)if (!st[i]){dfs(i);res ++;}cout << x << " " << res - x << endl;return 0;
}

E - Geometric Progression（重头戏）

原题

Problem Statement

Given integers AAA, XXX, and MMM, find ∑i=0X−1Ai\displaystyle \sum_{i = 0}^{X-1} A^ii=0∑X−1​Ai, modulo MMM.

Constraints

1≤A,M≤1091 \leq A, M \leq 10^91≤A,M≤109
1≤X≤10121 \leq X \leq 10^{12}1≤X≤1012
All values in the input are integers.

Input

The input is given from Standard Input in the following format:
AAA XXX MMM

Output

Print the answer.

Sample Input 1

3 4 7

Sample Output 1

5
30+31+32+33=403^0 + 3^1 + 3^2 + 3^3 = 4030+31+32+33=40, which equals 555 modulo 777, so 555 should be printed.

Sample Input 2

8 10 9

Sample Output 2

0

Sample Input 3

1000000000 1000000000000 998244353

Sample Output 3

919667211

题目大意

就是算出∑i=0X−1Ai\displaystyle \sum_{i = 0}^{X-1} A^ii=0∑X−1​Ai, 模MMM的值

思路

∑i=0X−1Ai\displaystyle \sum_{i = 0}^{X-1} A^ii=0∑X−1​Ai等于A0+A1+⋯+Ax−2+Ax−1A^0 + A^1 + \dots + A^{x-2} + A^{x-1}A0+A1+⋯+Ax−2+Ax−1，此时就发现其实就是将A进制数下的1111111…1111111111\dots 1111111111…111转为十进制数。

设ttt为X−1X-1X−1，
那么ttt一定可以分解为(111…111)2、(111)2、…、21、20(111\dots111)_2 、(111)_2、\dots、2^1、2^0(111…111)2​、(111)2​、…、21、20这些数中某几个数的和！

浅浅的证明：

因为2^0是1，所以任何数至少可以分成好几个1相加！

之后我们可以转化为：
∑i=0tAi=A0+A1+⋯+At−1+At=(1+A(1)2+A(10)2+A(11)2+⋯+A(11…111(s−1个))2+A(10…001)2+…=∑i=0s−1Ai+∑i=sy−1Ai+∑i=yz−1Ai+…=∑i=0s−1Ai+As∑i=0y−s−1Ai+Ay∑i=0z−y−1Ai+…\begin{align*} \displaystyle \sum_{i = 0}^{t} A^i&= A^0 + A^1 + \dots + A^{t-1} + A^{t} \\ &= (1+A^{(1)_2}+A^{(10)_2}+A^{(11)_2}+\dots+A^{(11\dots111(s-1个))_2} + A^{(10\dots001)_2}+\dots\\ &= \displaystyle \sum_{i = 0}^{s-1} A^i + \displaystyle \sum_{i = s}^{y - 1} A^i + \displaystyle \sum_{i = y}^{z - 1} A^i + \dots \\ &=\displaystyle \sum_{i = 0}^{s - 1} A^i + A^s\displaystyle \sum_{i = 0}^{y - s - 1} A^i + A^y\displaystyle \sum_{i = 0}^{z-y-1} A^i+\dots \end{align*} i=0∑t​Ai​=A0+A1+⋯+At−1+At=(1+A(1)2​+A(10)2​+A(11)2​+⋯+A(11…111(s−1个))2​+A(10…001)2​+…=i=0∑s−1​Ai+i=s∑y−1​Ai+i=y∑z−1​Ai+…=i=0∑s−1​Ai+Asi=0∑y−s−1​Ai+Ayi=0∑z−y−1​Ai+…​
这里s−1,y−s−1,z−y−1s-1,y-s-1,z-y-1s−1,y−s−1,z−y−1全是(111…111)2(111\dots111)_2(111…111)2​或0，如:
∑i=011Ai=A0+A1+⋯+A10+A11=∑i=07Ai+∑i=811Ai=∑i=07Ai+A8∑i=03Ai\begin{align*} \displaystyle \sum_{i = 0}^{11} A^i&= A^0 + A^1 + \dots + A^{10} + A^{11} \\ &= \displaystyle \sum_{i = 0}^{7} A^i + \displaystyle \sum_{i = 8}^{11} A^i\\ &=\displaystyle \sum_{i = 0}^{7} A^i + A^8\displaystyle \sum_{i = 0}^{3} A^i \end{align*} i=0∑11​Ai​=A0+A1+⋯+A10+A11=i=0∑7​Ai+i=8∑11​Ai=i=0∑7​Ai+A8i=0∑3​Ai​

所以，我们可以先把这个∑i=00Ai，∑i=01Ai，∑i=03Ai，∑i=07Ai，…\displaystyle \sum_{i = 0}^{0} A^i，\displaystyle \sum_{i = 0}^{1} A^i，\displaystyle \sum_{i = 0}^{3} A^i，\displaystyle \sum_{i = 0}^{7} A^i，\dotsi=0∑0​Ai，i=0∑1​Ai，i=0∑3​Ai，i=0∑7​Ai，…预处理出来！
那么预处理到多少呢？
答案是：239−12^{39}-1239−1
因为x小于等于101210^{12}1012，而240−12^{40}-1240−1大于101210^{12}1012，所以处理到239−12^{39}-1239−1就可以了

那么怎么计算呢？
我们先处理出∑i=00Ai\displaystyle \sum_{i = 0}^{0} A^ii=0∑0​Ai,就是1！然后我们递推的求出之后的每一个。
递推公式：(t为当前算第几个数）
∑i=02t−1Ai=∑i=02(t−1)−1Ai×(A2t−1+1)\begin{align*} \displaystyle \sum_{i = 0}^{2^t-1} A^i = \displaystyle \sum_{i = 0}^{2^{(t - 1)}-1} A^i \times (A^{2^{t-1}} + 1) \end{align*} i=0∑2t−1​Ai=i=0∑2(t−1)−1​Ai×(A2t−1+1)​

然后，我们发现是s, y, z,都是2的整数次幂，所以我们也提前与处理出来A20,A21,…,A239A^{2^0},A^{2^1},\dots,A^{2^{39}}A20,A21,…,A239就可以了！

最后，按照公式加起来就可以了！

注意：

1. 要用long long
2. 注意不能用1<<1<<1<<，因为超过32时，会出错（亲测）
3. 要用快速幂！

相信大家都不喜欢看长长的证明，那么香香的代码送你们了

代码

#include 
#include 
#include 
#define int long long
#define endl '\n'
#define pb(i) push_back(i)using namespace std;inline int read()
{int w = 1, s = 0;char c = getchar();while (c < '0' || c > '9'){if (c == '-') w = -1;c = getchar();}while (c >= '0' && c <= '9') s = s * 10 + c - '0', c = getchar();return w * s;
}inline int qmi(int a, int b, int p)
{int res = 1;while (b){if (b & 1) res = (res * a) % p;a = a * a % p;b >>= 1;}return res;
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int a, x, m;cin >> a >> x >> m;deque sgm, pw;//预处理sgm.pb(1);pw.pb(a % m);while (sgm.size() < 40)sgm.pb(sgm.back() * (qmi(a, (int)pow(2, sgm.size() - 1), m) + 1) % m);while (pw.size() < 40)pw.pb(pw.back() * pw.back() % m);//计算int res = 0, times = 1;for (int i = 39; i >= 0; i --){int t = pow(2, i);if (x >= t){res = (res + (sgm[i] * times % m)) % m;times = times * pw[i] % m;x -= t;}}	cout << res << endl;return 0;
}

今天就到这里了！

大家有什么问题尽管提，我都会尽力回答的！

吾欲您伸手，点的小赞赞。吾欲您喜欢，点得小关注！

（这两天比赛有点多，直到现在才发出来，非常抱歉~~~）