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}$$$.
Define free nodes $$$x$$$ — $$$free[x]=1$$$ means we can freely flip $$$x,fa[x]$$$,on the premise that we change all the descendant nodes(exclude itself) of $$$x$$$ to 0;
Define $$$col[x]$$$ — the value when node $$$x$$$ does not affect $$$fa[x]$$$,on the premise that we change all the descendant nodes(exclude itself) of $$$x$$$ to 0.Later on, we can see that this value is unique.
We update the values of $$$free[x],col[x]$$$ from bottom to top.
(coming soon)
Obviously,the length of a continuous segment with a negative contribution is $$$1$$$.
We can write a $$$O(n^2)$$$ DP:
$$$dp[i]=max{dp[j]-a[j+1]+a[j+2]|...|a[i]}$$$
Then we notice there're at most $$$O(log maxa)$$$ different values in $$$a[j]|...|ai$$$.It's a classic conclution.
For a fix $$$a[j]|...|a[i]$$$=t,we get $$$dp[i]=max{dp[j]-a[j+1]}+t$$$,then we can use a segment tree to maintain it.
In fact,use prefix maximum value is enough.Note $$$premax[i]=max(dp[1]-a[2],...,dp[i]-a[i+1])$$$,$$$dp[i]=premax[j]+t$$$.
This has prepared us for solving F2(solution2).
You need to observation that the length of consecutive segments will not exceed $$$60$$$.
Consider $$$aL...R$$$,there $$$>30$$$ such index $$$k$$$ satisfy $$$(a[k]|a[k+1]|...|a[R])=(a[k+1]|...|a[R])$$$;
Now let's consider such $$$>30$$$ such index $$$k$$$.
If $$$(a[L]|a[L+1]|...a[k-1])=(a[L]|a[L+1]|...a[k-1]|a[k])$$$ also holds,make partision $$$[a[L],...a[k-1]] [a[k]] [a[k+1],...a[R]]$$$ is better.
Otherwise we can infer $$$(a[L]|a[L+1]|...a[k-1])!=(a[L]|a[L+1]|...a[k-1]|a[k])$$$;
But there $$$>30$$$ such index $$$k$$$,contradiction.
Then we can use a scrolling array for DP.