If $$$n=6k$$$,print $$$0...0$$$;
If $$$n=6k+1$$$,print $$$0...08$$$;
If $$$n=6k+2$$$,print
Unable to parse markup [type=CF_MATHJAX]
;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,2,2n-1,...,n,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.
Case $$$1$$$:$$$x$$$ has $$$0$$$ son nodes.It's easy to get $$$free[x]=0,col[x]=a[x]$$$.
Case $$$2$$$:$$$x$$$ has $$$1$$$ son nodes.
We get $$$free[x]=0$$$.
If $$$col[son[x][0]]=0$$$,we don't need to flip $$$son[x][0]$$$ and $$$x$$$,$$$col[x]=a[x]$$$;
If $$$col[son[x][0]]=1$$$ and $$$free[son[x][0]]=0$$$,no solution.Otherwise we must flip $$$son[x][0]$$$ and $$$x$$$,$$$col[x]=a[x]⊕1$$$;
Case $$$3$$$:$$$x$$$ has $$$>2$$$ son nodes.
Note $$$tagc$$$ as the xor value of col values of all child nodes of $$$x$$$.If $$$tagc=1$$$ and there're no free nodes in $$$son[x][i]$$$,no solution.
If we can change all the descendant nodes(exclude itself) of $$$x$$$ to 0,$$$x$$$ is always a free node.
We can do flip $$$x,fa[x],son[x][1],son[x][2]$$$,flip $$$x,fa[x],son[x][2],son[x][3]$$$ and flip $$$x,fa[x],son[x][1],son[x][3]$$$ to only flip $$$x,fa[x]$$$.
Let's calculate $$$col[x]$$$.If $$$tagc=1$$$,we must flip $$$x$$$ and a free node,so $$$col[x]=a[x]⊕1$$$.If $$$tagc=0$$$,$$$col[x]=a[x]⊕0$$$.
Case $$$4$$$:$$$x$$$ has $$$2$$$ son nodes.
If $$$son[x][1],son[x][2]$$$ are both not free nod:
if $$$col[son[x][1]]⊕col[son[x][2]]=1$$$,no solution;
if $$$col[son[x][1]]=col[son[x][2]]=0$$$,$$$free[x]=0,col[x]=a[x]$$$;
if $$$col[son[x][1]]=col[son[x][2]]=1$$$,$$$free[x]=0,col[x]=a[x]⊕1$$$,and flip $$$a[fa[x]]$$$;
If $$$son[x][1],son[x][2]$$$ are both free node,$$$free[x]=1,col[x]=a[x]⊕col[son[x][1]]⊕col[son[x][2]]$$$.
Otherwise,do similar casework :)
Finally(I promise),let's check the answer,for all son nodes of node $$$1$$$:
Note $$$tagc$$$ as the xor value of col values of all child nodes of $$$1$$$.If $$$tagc=1$$$ and there're no free nodes in $$$son[1][i]$$$,no solution.
Otherwise,we should check $$$a[1]⊕tagc$$$.The answer is $$$YES$$$ if and only if $$$a[1]⊕tagc=0$$$.
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)$$$.
For $$$k>2,dp[j]-a[j+1]+(a[j+k]|...|a[i]) \leq dp[j]-a[j+1]+(a[j+2]|...|a[i])$$$
We can see adding some 'illegal' transfers will not make the solution bigger.
This has prepared us for solving F2(solution2).
You need to observation that the length of consecutive segments will not exceed $$$60$$$.
Consider $$$a[L...R]$$$ $$$(R-L+1>60)$$$ ,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.