A permutation of length n is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array) and [1,3,4] is also not a permutation (n=3 but there is 4 in the array).
For a positive integer n, we call a permutation p of length n good if the following condition holds for every pair i and j (1 \le i \le j \le n) —
Given a positive integer $n$, output any good permutation of length $n$. We can show that for the given constraints such a permutation always exists.
#### Input:
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). Description of the test cases follows.
The first and only line of every test case contains a single integer $n$ ($1 \le n \le 100$).
#### Output
For every test, output any **good** permutation of length $n$ on a separate line.
#### Sample Input:
```
t
3
1
3
7
```
#### Sample Output:
```
t
1
3 1 2
4 3 5 2 7 1 6
```
### 思路
因为**任意两个数或起来只增不减**，且长度大于 l 的序列一定存在一个大于 l 的数，所以我们随便输出一个序列即可
### 实现
```cpp
#include "ybwhead/ios.h"
int main()
{
int TTT;
yin >> TTT;
while (TTT--)
{
int n;
yin >> n;
for (int i = 1; i <= n; i++)
{
yout << i << " ";
}
yout << endl;
}
return 0;
}
```
## B. Fix You
### 题面
> Time: 1 second
> Memory: 256 megabytes
#### Description:
Consider a conveyor belt represented using a grid consisting of $n$ rows and $m$ columns. The cell in the $i$-th row from the top and the $j$-th column from the left is labelled $(i,j)$.
Every cell, except $(n,m)$, has a direction R (Right) or D (Down) assigned to it. If the cell $(i,j)$ is assigned direction R, any luggage kept on that will move to the cell $(i,j+1)$. Similarly, if the cell $(i,j)$ is assigned direction D, any luggage kept on that will move to the cell $(i+1,j)$. If at any moment, the luggage moves out of the grid, it is considered to be lost.
There is a counter at the cell $(n,m)$ from where all luggage is picked. A conveyor belt is called functional if and only if any luggage reaches the counter regardless of which cell it is placed in initially. More formally, for every cell $(i,j)$, any luggage placed in this cell should eventually end up in the cell $(n,m)$.
This may not hold initially; you are, however, allowed to change the directions of some cells to make the conveyor belt functional. Please determine the minimum amount of cells you have to change.
Please note that it is always possible to make any conveyor belt functional by changing the directions of some set of cells.
#### Input:
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10$). Description of the test cases follows.
The first line of each test case contains two integers $n, m$ ($1 \le n \le 100$, $1 \le m \le 100$) — the number of rows and columns, respectively.
The following $n$ lines each contain $m$ characters. The $j$-th character in the $i$-th line, $a_{i,j}$ is the initial direction of the cell $(i, j)$. Please note that $a_{n,m}=$ C.
#### Output
For each case, output in a new line the minimum number of cells that you have to change to make the conveyor belt functional.
#### Sample Input:
```
t
4
3 3
RRD
DDR
RRC
1 4
DDDC
6 9
RDDDDDRRR
RRDDRRDDD
RRDRDRRDR
DDDDRDDRR
DRRDRDDDR
DDRDRRDDC
1 1
C
```
#### Sample Output:
```
t
1
3
9
0
```
### 思路
一个非$(n,i)$或$(i,m)$的格点一定可以走到第$n$行或者第$m$列，所以只要判断第$n$行和第$m$列合不合法即可
### 实现
```cpp
#include "ybwhead/ios.h"
int main()
{
int TTT;
yin >> TTT;
while (TTT--)
{
int n, m;
yin >> n >> m;
int ans = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
char c;
yin >> c;
if (i == n)
ans += c == 'D';
if (j == m)
ans += c == 'R';
}
}
yout << ans << endl;
}
return 0;
}
```
## C. Cyclic Permutations
### 题面
> Time: 1 second
> Memory: 256 megabytes
#### Description:
A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).
Consider a permutation $p$ of length $n$, we build a graph of size $n$ using it as follows:
For every $1 \leq i \leq n$, find the largest $j$ such that $1 \leq j < i$ and $p_j > p_i$, and add an undirected edge between node $i$ and node $j$ For every $1 \leq i \leq n$, find the smallest $j$ such that $i < j \leq n$ and $p_j > p_i$, and add an undirected edge between node $i$ and node $j$ In cases where no such $j$ exists, we make no edges. Also, note that we make edges between the corresponding indices, not the values at those indices.
For clarity, consider as an example $n = 4$, and $p = [3,1,4,2]$; here, the edges of the graph are $(1,3),(2,1),(2,3),(4,3)$.
A permutation $p$ is cyclic if the graph built using $p$ has at least one simple cycle.
Given $n$, find the number of cyclic permutations of length $n$. Since the number may be very large, output it modulo $10^9+7$.
Please refer to the Notes section for the formal definition of a simple cycle
#### Input:
The first and only line contains a single integer $n$ ($3 \le n \le 10^6$).
#### Output
Output a single integer $0 \leq x < 10^9+7$, the number of cyclic permutations of length $n$ modulo $10^9+7$.
#### Sample Input:
```
t
4
```
#### Sample Output:
```
t
16
```
#### Sample Input:
```
t
583291
```
#### Sample Output:
```
t
135712853
```
### 思路
我们先对答案进行容斥。设$ans_n=n!-d_n$, $P_i$表示第$i$个点在第$P_i$这个位置。
**有一个结论：如果$\vert P_n-P_{n-1}\vert >1$就一定合法**
> ##### _证明_
>
> 设$l=\min(P_n,P_{n-1})$,$r=max(P_n,P_{n-1})$,$x=\max\limits_{l}^r p_i
则l,r,P_x形成一个环。
所以我们只能将最大和次大值放在一起，每次有两种选择(放在左边或者右边)。
所以d_n=\prod\limits_{1}^{n-1}2=2^{n-1}
这个序列是 oeis 上的一个序列。
实现
#include "ybwhead/ios.h"
const long long mod = 1e9 + 7;
long long ksm(long long a, int n)
{
long long ans = 1;
while (n)
{
if (n & 1)
ans = (ans * a) % mod;
a = (a * a) % mod;
n >>= 1;
}
return ans;
}
int main()
{
long long n;
yin >> n;
long long ans = 1;
for (long long i = 1; i <= n; i++)
{
ans *= i;
ans %= mod;
}
yout << (ans - ksm(2, n - 1) + mod) % mod << endl;
return 0;
}
D. 505
题面
Time: 1 second
Memory: 256 megabytes
Description:
A binary matrix is called good if every even length square sub-matrix has an odd number of ones.
Given a binary matrix a consisting of n rows and m columns, determine the minimum number of cells you need to change to make it good, or report that there is no way to make it good at all.
All the terms above have their usual meanings — refer to the Notes section for their formal definitions.
Input:
The first line of input contains two integers n and m (1 \leq n \leq m \leq 10^6 and n\cdot m \leq 10^6) — the number of rows and columns in a, respectively.
The following n lines each contain m characters, each of which is one of 0 and 1. If the j-th character on the i-th line is 1, then a_{i,j} = 1. Similarly, if the j-th character on the i-th line is 0, then a_{i,j} = 0.
Output
Output the minimum number of cells you need to change to make a good, or output -1 if it's not possible at all.
Sample Input:
t
3 3
101
001
110
Sample Output:
t
2
Sample Input:
t
7 15
000100001010010
100111010110001
101101111100100
010000111111010
111010010100001
000011001111101
111111011010011
#include "ybwhead/ios.h"
const int maxn = 1e6 + 10;
char c[maxn][4];
int f[maxn][8];
int a[10], b[10];
int main()
{
int n, m;
yin >> n >> m;
if (n >= 4 && m >= 4)
{
puts("-1");
return 0;
}
if (n > m)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
yin >> c[i][j];
}
}
swap(n, m);
}
else
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
yin >> c[j][i];
}
}
}
if (n == 1)
{
puts("0");
return 0;
}
for (int i = 0; i < 8; i++)
{
if (i >= 4 && n == 2)
break;
for (int kk = 1; kk <= n; kk++)
if (i & (1 << (kk - 1)))
a[kk] = 1;
else
a[kk] = 0;
int ans = 0;
for (int kk = 1; kk <= n; kk++)
if (a[kk] != c[1][kk] - '0')
ans++;
f[1][i] = ans;
}
for (int k = 2; k <= m; k++)
{
for (int i = 0; i < 8; i++)
{
if (i >= 4 && n == 2)
break;
f[k][i] = INT_MAX;
for (int j = 0; j < 8; j++)
{
if (j >= 4 && n == 2)
break;
for (int kk = 1; kk <= n; kk++)
if (i & (1 << (kk - 1)))
a[kk] = 1;
else
a[kk] = 0;
for (int kk = 1; kk <= n; kk++)
if (j & (1 << (kk - 1)))
b[kk] = 1;
else
b[kk] = 0;
int ans = 0;
for (int kk = 1; kk <= n; kk++)
if (a[kk] != c[k][kk] - '0')
ans++;
if ((a[1] + a[2] + b[1] + b[2]) & 1)
if (n == 2 || ((a[2] + a[3] + b[2] + b[3]) & 1))
f[k][i] = min(f[k][i], f[k - 1][j] + ans);
}
}
}
if (n == 2)
{
int ans = INT_MAX;
for (int i = 0; i < 4; i++)
ans = min(ans, f[m][i]);
yout << ans << endl;
return 0;
}
int ans = INT_MAX;
for (int i = 0; i < 8; i++)
ans = min(ans, f[m][i]);
yout << ans << endl;
return 0;
}
E. Pairs of Pairs
题面
Time: 3 seconds
Memory: 256 megabytes
Description:
You have a simple and connected undirected graph consisting of n nodes and m edges.
Consider any way to pair some subset of these n nodes such that no node is present in more than one pair.
This pairing is valid if for every pair of pairs, the induced subgraph containing all 4 nodes, two from each pair, has at most 2 edges (out of the 6 possible edges). More formally, for any two pairs, (a,b) and (c,d), the induced subgraph with nodes \{a,b,c,d\} should have at most 2 edges.
Please note that the subgraph induced by a set of nodes contains nodes only from this set and edges which have both of its end points in this set.
Now, do one of the following:
Find a simple path consisting of at least \lceil \frac{n}{2} \rceil nodes. Here, a path is called simple if it does not visit any node multiple times. Find a valid pairing in which at least \lceil \frac{n}{2} \rceil nodes are paired. It can be shown that it is possible to find at least one of the two in every graph satisfying constraints from the statement.
Input:
Each test contains multiple test cases. The first line contains the number of test cases t (1 \le t \le 10^5). Description of the test cases follows.
The first line of each test case contains 2 integers n, m (2 \le n \le 5\cdot 10^5, 1 \le m \le 10^6), denoting the number of nodes and edges, respectively.
The next m lines each contain 2 integers u and v (1 \le u, v \le n, u \neq v), denoting that there is an undirected edge between nodes u and v in the given graph.
It is guaranteed that the given graph is connected, and simple — it does not contain multiple edges between the same pair of nodes, nor does it have any self-loops.
It is guaranteed that the sum of n over all test cases does not exceed 5\cdot 10^5.
It is guaranteed that the sum of m over all test cases does not exceed 10^6.
Output
For each test case, the output format is as follows.
If you have found a pairing, in the first line output "PAIRING" (without quotes).
Then, output k (\lceil \frac{n}{2} \rceil \le 2\cdot k \le n), the number of pairs in your pairing. Then, in each of the next k lines, output 2 integers a and b — denoting that a and b are paired with each other. Note that the graph does not have to have an edge between a and b! This pairing has to be valid, and every node has to be a part of at most 1 pair. Otherwise, in the first line output "PATH" (without quotes).
Then, output k (\lceil \frac{n}{2} \rceil \le k \le n), the number of nodes in your path. Then, in the second line, output k integers, v_1, v_2, \ldots, v_k, in the order in which they appear on the path. Formally, v_i and v_{i+1} should have an edge between them for every i (1 \le i < k). This path has to be simple, meaning no node should appear more than once.