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$$$.

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$$$.

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]|...|a[i]$$$ $$$(j<i)$$$.It's a classic conclution.

For a fix $$$a[j]|...|a[i]$$$ $$$=t$$$,we get $$$dp[i]=max(dp[j]-a[j+1])+t$$$.Since the value range of $$$j$$$ is continuous,we can use a segment tree to maintain it.It's $$$O(n log^2 n)$$$.

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$$$.It's $$$O(n log n)$$$.

This has prepared us for solving F2(solution2).

You need to observation that the length of consecutive segments will not exceed $$$60$$$.

Then we can use a scrolling array for DP.