If $$$n=6k$$$,print $$$0...0$$$;
If $$$n=6k+1$$$,print $$$0...08$$$;
If $$$n=6k+2$$$,print $$$0...01$$$;
If $$$n=6k+3$$$,print $$$0...07$$$;
If $$$n=6k+4$$$,print $$$0...04$$$;
If $$$n=6k+5$$$,print $$$0...05$$$;
If $$$n=6k+6$$$,print $$$0...09$$$.
First,maximize number of digits — fill each digit with $$$'1'$$$.
Then starting from the highest bit,consider maximizing the current digit — consider changing the current bit to $$$'9'$$$. If no enough matchsticks, consider $$$'7'$$$.
Luckily,you find $$$[1,2n-1,3,2n-3,...,n-1,n+1]$$$ works :)
Note $$$s_1=p_1+p_2=p_3+p_4=...=p_{2n-1}+p_{2n},s_2=p_2+p_3=p_4+p_5=...=p_{2n-2}+p_{2n-1}$$$.
We can easily get $$$s_1=2n+1$$$.
Consider fix $$$s_2$$$,we can get:$$$p_{2n}=n*s_1-p_1-(n-1)s_2$$$.Since $$$1\leq p_{2n} \leq 2n$$$, we found that there are no more than $$$3$$$ suitable $$$s_2$$$.
Consider changing $$$s_2$$$ by $$$1$$$,then $$$p_{2n}$$$ will change $$$n-1$$$.
For each suitable $$$s_2$$$,we can calculate the whole array,and check if it’s a permutation in $$$O(n)$$$.
Consider a $$$3*3$$$ matrix,we can do something like:
$$$000$$$
$$$000$$$
$$$000$$$
$$$->$$$
$$$100$$$
$$$010$$$
$$$101$$$
$$$->$$$
$$$101$$$
$$$000$$$
$$$000$$$
Consider we can only flip $$$a_{x,y},a_{x,y+2}$$$ and $$$a_{x,y},a_{x+2,y}$$$,what about the answer?
Note $$$x_0=a_{1,1}⊕a_{1,3}⊕...,x_1=a_{1,2}⊕a_{1,4}⊕...$$$,the answer is $$$YES$$$ if and only if the $$$x_0=x_1=0$$$.
If you don't know, it means you haven't read #11 F's editorial
Let's go back to the original problem.The only difference is there are some unaccessable elements.Just do special judgment.
If $$$n=3,m=3$$$,unaccessable elements are $$$a_{1,2},a_{2,1},a_{2,3},a_{3,2}$$$;
If $$$n=3,m=4$$$,unaccessable elements are $$$a_{2,1},a_{2,4}$$$;
If $$$n=4,m=3$$$,unaccessable elements are $$$a_{1,2},a_{4,2}$$$.
Consider an easier problem:for a fixed score $$$x_1*x_2*...*x_k$$$($$$x_i$$$ is one of the prefix minimum value and note the set of them as $$$X$$$),how to calculate the number of schemes?
Consider such a sequence construction process: put all $$$0$$$'s, all $$$1$$$'s, and all $$$2$$$'s,...
If you want the prefix minimum value of $$$i$$$ to appear in $$$a$$$, what should you do?We can get:at least one $$$i$$$ must be placed at the head of the current sequence.
This is actually equivalent to the classical problem: $$$m_i$$$ balls are put into $$$(m_1+...+m_{i-1}+1)$$$ boxes, the first box must have at least one ball,count the number of schemes.
The answer is:
$$$U_i=C(m_i-1+(m_1+...+m_{i-1}),(m_1+...+m_{i-1}))$$$.
If you want the prefix minimum value of i not to appear in $$$a$$$, what should you do?We can get:no $$$i$$$ must be placed at the head of the sequence.Solve it in a similar way as above.
The answer is:
$$$V_i=C(m_i+(m_1+...+m_{i-1})-1,(m_1+...+m_{i-1})-1)$$$.
Let's go back to the easier problem.The number of schemes is $$$\Pi_{i∈X}U_i * \Pi_{i∉X}V_i$$$.
Finally, how to calculate the total score?We can convert the formula into:$$$(1*U_1+V_1)(2*U_2+V_2)...(n*U_n+V_n)$$$.
Consider its extended form. Each item corresponds to a specific set $$$X$$$.
There's another dp solution:$$$dp_i=(i-1)*U_{i-1}*dp_{i-1}+V_{i-1}*dp_{i-1}$$$.It's actually do the same thing.
Note $$$c_{i,j}=a_{i,j}⊕b_{i,j}$$$.The problem is equivalent to turning $$$c$$$ into a zero matrix.
Consider $$$l=2$$$.What about the solution?
We can easily get:the answer is $$$YES$$$ if and only if the xor-sum of all numbers is $$$0$$$.
For an operation,you can do:
Flip two adjacent $$$1$$$ to $$$0$$$
Move an $$$1$$$ one position in any direction
Using these two operations,we can easily make $$$c$$$ a zero matrix.
Now let’s consider $$$l=3$$$.The method can be extended to $$$l=k$$$.
We notice we can do:
$$$0000->1110->1001$$$
If we can only filp $$${a_{x,y},a_{x,y+3}}$$$ and $$${a_{x,y},a_{x+3,y}}$$$,what about the answer?
We group the elements in the matrix $$$c$$$ like:
$$$1231231... $$$
$$$4564564... $$$
$$$7897897... $$$
$$$1231231... $$$
$$$... $$$
Note $$$XOR(i)$$$ as xor-sum of all numbers in group $$$i$$$.We can get:if all $$$XOR(i)$$$ are $$$0$$$,the answer is $$$YES$$$.
Consider only the new matrix composed of the $$$i^{th}$$$ group,we find the problem is equivalent to the case when $$$l=2$$$.
Now let’s consider the origin flip. In essence,there are only $$$6$$$ different operations:
Flip $$$XOR(1),XOR(2),XOR(3)$$$;
Flip $$$XOR(4),XOR(5),XOR(6)$$$;
Flip $$$XOR(7),XOR(8),XOR(9)$$$;
Flip $$$XOR(1),XOR(4),XOR(7)$$$;
Flip $$$XOR(2),XOR(5),XOR(8)$$$;
Flip $$$XOR(3),XOR(6),XOR(9)$$$.
Construct a $$$l*l$$$ matrix $$$d$$$,$$$d_{i,j}=XOR((i-1)*l+j)$$$.We find that we can turn it into a classical problem:
What about $$$x*y$$$ span?