Official

Overall Editorial by evima

Hints

A - Flip Row or Col 2

Hint 1 The key point of this problem is the constraint $R_i,C_j\lt N/4$. Let's think about how to utilize this constraint.
Hint 2 By initially performing appropriate column flips, we can assume that all elements in the first row of $A$ are $0$.
Hint 3 Starting from a state where all elements in the first row of $A$ are $0$, we perform operations in the order of row flip → column flip. At this point, whether each row should be flipped is uniquely determined by focusing on a certain aspect.
Hint 4 Column flips can be performed at most $(N-1)/4$ times.
Hint 5 After row flips are completed, the sum of each row must be at most $N/2$.

Editorial: https://atcoder.jp/contests/arc199/editorial/13175

B - Adjacent Replace

Hint 1 This problem can be broadly divided into two parts. The first is the decision part of whether $K$ can be created, and the second is the construction part of how to actually perform the operations.
Hint 2 First, let's consider what numbers can be created when $A=(2^0,2^1,\ldots,2^{N-1})$.
Answer to Hint 2 When $A=(2^0,2^1,\ldots,2^{N-1})$, the values of $K$ that can be created are those satisfying $0\leq K\lt 2^N$ and $K\neq 2^0\oplus 2^2\oplus 2^4\oplus\dots$ and $K\neq 2^1\oplus 2^3\oplus 2^5\oplus\dots$.
Hint 3 When $A=(2^0,2^1,\ldots,2^{N-1})$ and $K$ can be created, let's think about the actual procedure to create it. For example, when there exists $j\ (0\leq j\leq N-2)$ such that $K\ \mathrm{AND}\ 2^j=0\land\ K\mathrm{AND}\ 2^{j+1}=0$, what kind of operation strategy can be established?
Hint 4 For the general case of $A$, it suffices to determine whether there exists a set $S$ satisfying $\displaystyle\bigoplus_{i\in S}A_i=K\land S\neq \lbrace 1,3,5,\ldots\rbrace\wedge S\neq \lbrace 2,4,6,\ldots\rbrace$. This can be found using Gaussian elimination.

Editorial: https://atcoder.jp/contests/arc199/editorial/13176

C - Circular Tree Embedding

Hint 1 First, let's consider the case where $M=1$ and $P^1=(1,2,\ldots,N)$. What properties do trees for which this $P^1$ is a good permutation have?
Hint 2 Consider the tree as a rooted tree with vertex $1$ as the root. For rooted trees where $(1,2,\ldots,N)$ is a good permutation, think about the necessary and sufficient conditions by focusing on the vertex sets of subtrees.
Answer to Hint 2 The vertex set of any subtree of the rooted tree, when appropriately rearranged, forms a contiguous subsequence of $(1,2,\ldots,N)$. This is the necessary and sufficient condition.
Hint 3 Since $P^i$ being a good permutation is equivalent to $((P^i_1+k\ \mathrm{mod} \ N) + 1,(P^i_2+k\ \mathrm{mod} \ N) + 1,\ldots,(P^i_N+k\ \mathrm{mod} \ N) + 1)$ being a good permutation, we can assume $P^i_1=1$. For a general permutation $P^i$ (with $P^i_1=1$), rooted trees for which $P^i$ is a good permutation have the property that the vertex set of any subtree, when appropriately rearranged, forms a contiguous subsequence of the inverse permutation of $P^i$.
Hint 4 For each $P^i$, there are $N(N+1)/2$ possible vertex sets for subtrees. When we find these sets for each of $P^1,P^2,\ldots$, only the sets that appear in all of them can be vertex sets of subtrees in rooted trees satisfying the conditions.
By the way, we can transform all permutations simultaneously so that $P^1=(1,2,\ldots,N)$. With this transformation, the vertex sets of rooted trees satisfying the conditions can be expressed as $\lbrace l,l+1,\ldots,r\rbrace$.
Hint 5 Finally, we can count using interval DP with $\mathrm{dp}[l][r]$ representing "the number of ways for subtrees with vertex set $\lbrace l,l+1,\ldots,r\rbrace$".

Editorial: https://atcoder.jp/contests/arc199/editorial/13177

D - Limestone

Hint 1 First, let's think about how to find the number of matrices that can be created. The same method used to find this can also be used to solve the problem of finding the total sum of $\sum A$.
Hint 2 You can generate matrix $A$ by deciding how many elements to set to $1$ from the left in each row, and how many elements to set to $1$ from the top in each column. While there are generally multiple ways to generate a certain $A$, you can create a bijection between $A$ and generation methods by characterizing the generation methods.
Hint 3 When setting $R_i$ elements to $1$ from the left in row $i$, and $C_j$ elements to $1$ from the top in column $j$, it's good to characterize by taking the lexicographically largest $R$ among the $R,C$ that generate a certain $A$, and then the lexicographically largest $C$ among those.
Hint 4 Let $S$ be the set of pairs $(R,C)$ that satisfy the conditions characterized in Hint 3. When $R$ is fixed, think about how to find the number of $C'$ such that $(R,C')\in S$ in $O(H+W)$ time.
Hint 5 You can find the number of $A$ using DP that keys on the important points when considering the problem in Hint 4.

Editorial: https://atcoder.jp/contests/arc199/editorial/13178

posted:
last update: