Codeforces Round ＃804 (Div. 2) - A, B, C

https://codeforces.com/contest/1699

---

C. The Third Problem

The question
Given a $0$ To $n-1$ The whole arrangement , Ask how many $0$ To $n-1$ The full arrangement of is similar to this arrangement ？
The answer is right 1e9+7 modulus .

Similarity definition ： If two full permutations meet the following conditions , Let's say that the two are similar in full arrangement .

• For any interval $[l,r](1\le l\le r\le n)$ All satisfied with ：$\mathrm{MEX}([a_l,a_{l+1},\dots ,a_r])=\mathrm{MEX}([b_l,b_{l+1},\dots ,b_r])$

For a pile of numbers $c_1,c_2,\dots ,c_k$ Of $\mathrm{MEX}$ Refer to , In collection $c$ The first non negative integer that does not appear in $x$.

Ideas
from 0 To n-1, Count one by one , See where it can be placed . Multiplication of all possible positions is the answer .

Number of tags x The position in the original arrangement is p[x].

• First, it's easy to determine ,0 and 1 The position in a similar arrangement does not change , All for p[0]. set up l Is the left end position ,r Is the right end position .
• about 2：
  1. If p[2] be located [l, r] in , that 2 Can be placed in [l, r] All free locations in ;
  （2 Originally in [l, r] in , that $\mathrm{MEX}[l,r]$ To achieve 3 了 , So in a similar arrangement 2 Only on the [l, r] in ）
  2. otherwise ,2 It can only be placed in its original position p[2]; then p[2] take l perhaps r to update ;
  （2 Originally in [l, r] outside , that $\mathrm{MEX}[l,r]$ It can only reach 2,2 Can't be in [l, r] in ; And if its position changes , There will be intervals MEX Value change , So in this case 2 The position of the cannot be changed ）
• about 3：
  1. If p[3] be located [l, r] in , that 3 Can be placed in [l, r] All free locations in ;
  2. otherwise ,3 It can only be placed in its original position p[3]; then p[3] take l perhaps r to update ;
• …

Code

#include<bits/stdc++.h>
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N], p[N];

signed main(){
    
	Ios;
	cin >> T;
	while(T--)
	{
    
		cin >> n;
		for(int i=1;i<=n;i++) cin >> a[i], p[a[i]] = i;
		
		int ans = 1;
		
		int l = min(p[0], p[1]), r = max(p[0], p[1]);
		for(int i=2;i<n;i++)
		{
    
			if(p[i] > l && p[i] < r)
			{
    
				ans = ans * (r-l+1 - i) % mod;
			}
			else{
    
				if(p[i] < l) l = p[i];
				else r = p[i];
			}
		}
		cout << ans << endl;
	}
	
	return 0;
}

Experience
When there is no idea, you should calm down and push back bit by bit from the initial situation , Maybe there is a way to push .
Instead of looking at the sample and thinking ..

---

B. Almost Ternary Matrix

The question
Construct a n*m Of 01 matrix , bring ：

• For each location , In its directly adjacent position , There are exactly two locations that are different from this location element .

$2\le n,m\le 50$ And all are even .

Ideas
So constructed ：

6 8
1 0 0 1 1 0 0 1
0 1 1 0 0 1 1 0
0 1 1 0 0 1 1 0
1 0 0 1 1 0 0 1
1 0 0 1 1 0 0 1
0 1 1 0 0 1 1 0

Code

#include<bits/stdc++.h>
using namespace std;

const int N = 210, mod = 1e9+7;
int T, n, m;
int a[N] = {
    1, 0, 0, 1}, b[N] = {
    0, 1, 1, 0};
int ans[N][N];

signed main(){
    
	scanf("%d", &T);
	while(T--)
	{
    
		scanf("%d%d", &n, &m);
		for(int i=1;i<=n;i++)
		{
    
			for(int j=0;j<m;j++)
			{
    
				if(i%4 == 1 || i%4 == 0) ans[i][j] = a[j%4];
				else ans[i][j] = b[j%4];
			}
		}
		
		for(int i=1;i<=n;i++){
    
			for(int j=0;j<m;j++){
    
				printf("%d ", ans[i][j]);
			}
			printf("\n");
		}
	}
	
	return 0;
}

---

A. The Third Three Number Problem

The question
Give a number $n$, Find three numbers $a,b,c$ Satisfy ：

• $(a\oplus b)+(b\oplus c)+(a\oplus c)=n$

Output not found $-1$.

$1\le n\le 10^9,0\le a,b,c\le 10^9$

Ideas
from $a+b=a\oplus b+2\cdot (a$ & $b)$ You know ,$a\oplus b$ and $a+b$ Having the same parity .
that $n=(a\oplus b)+(b\oplus c)+(a\oplus c)$ Just like $(a+b)+(b+c)+(a+c)=2\cdot (a+b+c)$ Having the same parity , It must be an even number .

• When n by Odd number output -1.
• otherwise Make $b=c=0$, Then the original formula becomes ：$a+a=n$, that $a=\frac{n}{2}$.

Code

#include<bits/stdc++.h>
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N];

signed main(){
    
	Ios;
	cin >> T;
	while(T--)
	{
    
		cin >> n;
		if(n % 2 == 0) cout << n/2 << " " << 0 << " " << 0 << endl;
		else cout << -1 << endl;
	}
	
	return 0;
}

Experience
Focus on special circumstances .