Luogu 1146 coin flip

Title Description

There is a row of coins on the table , common NN gold , Each coin is facing up . Now turn all the coins upside down , The rule is that you can flip any... At a time N-1N−1 Coin （ Turned upside down to upside down , vice versa ）. Find the shortest sequence of operations （ Flip each time N-1 A coin becomes an operation ）.

Input format

A natural number NN（NN Is not greater than 100100 An even number of ）.

Output format

The first line contains an integer SS, Indicates the minimum number of operations required . Next SS Each line represents the status of coins on the table after each operation （ One line contains NN It's an integer （00 or 11）, Indicates the status of each coin ：00―― face up , and 11―― Reverse up , Extra spaces are not allowed ）.

In case of multiple operation schemes , Then only the dictionary order of the operation needs to be the smallest output .

notes ： Dictionary order of operations ： For one operation ,1 It means flip ,0 Indicates no inversion .

But what you need to output is the status of each operation ,0 Face up ,1 The opposite side is up .

I/o sample

Input #1 Copy

4

Output #1 Copy

4
0111
1100
0001
1111

Topic link ：https://www.luogu.com.cn/problem/P1146

Their thinking ：

Every time I turn n-1 A coin , Equivalent to turning one at a time , So a total of n Time .

Clearly stated in the title n For the even , So that is to say, if each coin turns n-1 Time , It is equivalent to turning every coin once , So the plan to flip a coin is ： Select each coin , Turn over other coins except this one .

Code ：

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

int main() {
	int n;
	scanf("%d", &n);
	printf("%d\n", n);
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= i; j++) printf("%d", (i-1)&1);
		for(int j = i + 1; j <= n; j++) printf("%d", i&1);
		printf("\n");
	}
	return 0;
}