#A — Calc↵
↵
Just directly print the given sum.↵
↵
Time Complexity: $O(1)$. [Click here for my submission.](https://atcoder.jp/contests/abc172/submissions/14750143)↵
↵
---↵
↵
#B — Minor Change↵
↵
The answer is simply the number of positions $i$ for which $S[i] \neq T[i]$. This is because we must make a move fixing each of those position, and each move can only make $S[i] = T[i]$ for one new position. Thus, we can iterate through the positions and count those where $S$ and $T$ differ, printing the total as our answer.↵
↵
Time Complexity: $O(|S|)$. [Click here for my submission.](https://atcoder.jp/contests/abc172/submissions/14750027)↵
↵
---↵
↵
#C — Tsundoku↵
↵
We apply two pointers. Iterate over the number of books to be read from desk A in decreasing order, starting with the greatest number of those books we could read without exceeding $K$ minutes. Maintain the sum of all books to be read from desk A. Then, while we can do so without exceeding $K$ minutes, add the next book from desk B to the list of books to be read. We can then consider the total number of books read between desk A and desk B as a possible answer, decrement the number of books from desk A, and continue. ↵
↵
The basic intuition is that as we decrease the number of books we read from desk A, the number of books we read from desk B monotonically increases. By processing the number of books to be read from desk A in order, we avoid having to recompute any sums, achieving a time complexity of $O(N+M)$.↵
↵
Time Complexity: $O(N+M)$. [Click here for my submission.](https://atcoder.jp/contests/abc172/submissions/14749792)↵
↵
---↵
↵
#D — Sum of Divisors↵
↵
Let's reframe the problem by considering the total contribution each divisor makes to the answer. For any given $i$, $i$ contributes $K$ to the sum for each $K$ from $1$ to $N$ such that $K$ is a multiple of $i$.↵
↵
Notice that the list of these $K$ is of the form $i$, $2i$, $3i$, ..., $\lfloor \frac{N}{i} \rfloor i$, noting that the last term is the greatest multiple of $i$ less than $N$. For simplicity, let $M = \lfloor \frac{N}{i} \rfloor.$ Then, the sum of this sequence is equal to $i + 2i + 3i + \cdots + Mi = i (1 + 2 + \cdots + M) = \frac{iM(M+1)}{2}.$↵
↵
Thus, by computing $M$ and the above product, we can compute each divisor's contribution to the answer in $O(1)$, giving us an $O(N)$ solution.↵
↵
Time Complexity: $O(N)$. [Click here for my submission.](https://atcoder.jp/contests/abc172/submissions/14747486)↵
↵
---↵
↵
#E — NEQ↵
↵
First, let's count the number of ways to choose $A$, irrespective of $B$. There are $\dbinom{M}{N}$ ways to choose the $N$ integers to appear in $A$ and $N!$ ways to arrange them, so we have $\dbinom{N}{M} N!$ choices for $A$ in total.↵
↵
Now, without loss of generality, assume the sequence $A$ is simply $1, 2, \cdots, N$, since the number of choices for $B$ doesn't depend on our sequence $A$. We want to count the number of sequences $B$ where there is no position $i$ such that $B_i = i$. ↵
↵
We do this using the principle of inclusion and exclusion. By PIE, we know that the number of sequences $B$ where $B_i \neq i$ for all $i$ is equal to the sum over all valid $j$ of $(-1)^j$ times the number of ways to create a sequence $B$ where at least $j$ positions $i$ have $B_i = i$.↵
↵
Thus, it remains to compute the number of ways to compute the number of sequences $B$ with at least $j$ equal positions. There are $\dbinom{N}{j}$ ways to choose $j$ positions where $B_i = i$. Then, it doesn't matter what we put in the remaining positions, so there are $\dbinom{M-j}{N-j}$ ways to choose the numbers and $(N-j)!$ ways to arrange them. Thus, the total number of ways to ensure that at least $j$ positions have $B_i = i$ is $\dbinom{N}{j} \dbinom{M-j}{N-j} (N-j)!$.↵
↵
By precomputing all relevant factorials and their modular inverses in $O(M)$, we can compute the above product in $O(1)$ for each $j$. We then sum these up using our PIE formula, giving us an $O(N+M)$ solution. Since $N \leq M$, this is simply $O(M)$.↵
↵
Time Complexity: $O(M)$. [Click here for my submission.](https://atcoder.jp/contests/abc172/submissions/14746808)↵
↵
---↵
↵
#F — Unfair Nim↵
↵
It is well known that the second player wins a game of Nim if and only if the bitwise XOR of the numbers of stones in each pile is equal to $0$. Thus, we want to make the equation $A_1 \wedge A_2 \wedge A_3 \wedge \cdots \wedge A_n = 0$. By taking the XOR of this equation with $A_3 \wedge A_4 \wedge \cdots \wedge A_n$, we have $A_1 \wedge A_2 = A_3 \wedge A_4 \wedge \cdots \wedge A_n.$ We can immediately compute the right-hand side, since it is fixed before we make our moves. Now, we want to find the largest $x$ between $1$ and $A_1$, inclusive, such that $x \wedge (A_1 + A_2 - x) = A_3 \wedge A_4 \wedge \cdots \wedge A_n.$↵
↵
We build $x$ via digit DP, determining the bits of $x$ from the most significant bit to the least significant bit. Let $a$ be the maximum possible value of $x$ thus far such that we have found a bit in which $x$ contains a $0$ while $A_1$ contains a $1$ (so, we know that no matter what bits we add to $a$ in the future, it will be less than $A_1$), or $-\infty$ if no such value exists thus far. Let $b$ be the value of $x$ such that thus far, all bits in $b$ are the same as those in $A_1$, or $-\infty$ if creating this value is impossible. Note that we cannot add a $1$ to $b$ if the corresponding bit in $A_1$ is a $0$, as this would make $b$ too large.↵
↵
Let $S = A_3 \wedge A_4 \wedge \cdots \wedge A_n.$ If $S$ contains a $0$ in any given bit, we know that $x$ and $A_1 + A_2 - x$ must either both contain a bit or neither must contain a bit. We can tell which case applies by determining whether after subtracting out all bits we've assigned so far, $A_1 + A_2$ is greater than $2^{k+1}$, where $k$ is the index of the current bit. This is because the sum of all future bits will be at most $2^{k+1} - 2$, so $A_1 + A_2 \geq 2^{k+1}$ both enables us to add two $1$s at position $b$ and forces us to do so. If we add a bit to both numbers, we add $2^k$ to $a$ and $b$, but set $b$ to $-\infty$ if $A_1$ contains a $0$ in position $k$. Otherwise, we don't add anything to either $a$ or $b$, but if $A_1$ contains a $1$ in position $k$, we can set $a$ to $\max(a, b)$, since now we've found a position in which $x < A_1$.↵
↵
If $S$ contains a $1$ in any given bit, we know that exactly one of $x$ and $A_1 + A_2 - x$ must contain a bit. Thus, we can add $2^k$ to $a$, because this will not make $a$ exceed $A_1$. If $A_1$ contains a $1$ in position $k$, we can also add $2^k$ to $b$, or we can alternatively assign a $0$ in order to guarantee that $x < A[1]$, allowing us to set $a$ to $\max(a, b)$. ↵
↵
At the end of this process, $a$ and $b$ are our possible values for $x$. Of course, if $a$ and $b$ are zero or $-\infty$, they can't work (the zero case fails because we cannot move every stone from the first pile). Moreover, we also must confirm that $a \wedge (A_1 + A_2 - a) = S$ in order to use $a$, and we must check the same equation for $b$. This is because the total bits we assign throughout our process may not equal $A_1 + A_2$, since the number of bits we assign is largely determined by $S$. (One countercase that demonstrates this issue is $N=3, A = 7, 5, 6$: our solution assigns one bit in position $2$, one bit in position $1$, and two bits in position $0$, but the total of these bits is $4 + 2 + 2 = 8 < 7+5.$) Then, we take the largest of these possible values for $x$ and subtract it from $A_1$ to get our answer.↵
↵
Time Complexity: $O(N + \log A_i).$ [Click here for my submission.](https://atcoder.jp/contests/abc172/submissions/14743239)↵
↵
---
↵
Just directly print the given sum.↵
↵
Time Complexity: $O(1)$. [Click here for my submission.](https://atcoder.jp/contests/abc172/submissions/14750143)↵
↵
---↵
↵
#B — Minor Change↵
↵
The answer is simply the number of positions $i$ for which $S[i] \neq T[i]$. This is because we must make a move fixing each of those position, and each move can only make $S[i] = T[i]$ for one new position. Thus, we can iterate through the positions and count those where $S$ and $T$ differ, printing the total as our answer.↵
↵
Time Complexity: $O(|S|)$. [Click here for my submission.](https://atcoder.jp/contests/abc172/submissions/14750027)↵
↵
---↵
↵
#C — Tsundoku↵
↵
We apply two pointers. Iterate over the number of books to be read from desk A in decreasing order, starting with the greatest number of those books we could read without exceeding $K$ minutes. Maintain the sum of all books to be read from desk A. Then, while we can do so without exceeding $K$ minutes, add the next book from desk B to the list of books to be read. We can then consider the total number of books read between desk A and desk B as a possible answer, decrement the number of books from desk A, and continue. ↵
↵
The basic intuition is that as we decrease the number of books we read from desk A, the number of books we read from desk B monotonically increases. By processing the number of books to be read from desk A in order, we avoid having to recompute any sums, achieving a time complexity of $O(N+M)$.↵
↵
Time Complexity: $O(N+M)$. [Click here for my submission.](https://atcoder.jp/contests/abc172/submissions/14749792)↵
↵
---↵
↵
#D — Sum of Divisors↵
↵
Let's reframe the problem by considering the total contribution each divisor makes to the answer. For any given $i$, $i$ contributes $K$ to the sum for each $K$ from $1$ to $N$ such that $K$ is a multiple of $i$.↵
↵
Notice that the list of these $K$ is of the form $i$, $2i$, $3i$, ..., $\lfloor \frac{N}{i} \rfloor i$, noting that the last term is the greatest multiple of $i$ less than $N$. For simplicity, let $M = \lfloor \frac{N}{i} \rfloor.$ Then, the sum of this sequence is equal to $i + 2i + 3i + \cdots + Mi = i (1 + 2 + \cdots + M) = \frac{iM(M+1)}{2}.$↵
↵
Thus, by computing $M$ and the above product, we can compute each divisor's contribution to the answer in $O(1)$, giving us an $O(N)$ solution.↵
↵
Time Complexity: $O(N)$. [Click here for my submission.](https://atcoder.jp/contests/abc172/submissions/14747486)↵
↵
---↵
↵
#E — NEQ↵
↵
First, let's count the number of ways to choose $A$, irrespective of $B$. There are $\dbinom{M}{N}$ ways to choose the $N$ integers to appear in $A$ and $N!$ ways to arrange them, so we have $\dbinom{N}{M} N!$ choices for $A$ in total.↵
↵
Now, without loss of generality, assume the sequence $A$ is simply $1, 2, \cdots, N$, since the number of choices for $B$ doesn't depend on our sequence $A$. We want to count the number of sequences $B$ where there is no position $i$ such that $B_i = i$. ↵
↵
We do this using the principle of inclusion and exclusion. By PIE, we know that the number of sequences $B$ where $B_i \neq i$ for all $i$ is equal to the sum over all valid $j$ of $(-1)^j$ times the number of ways to create a sequence $B$ where at least $j$ positions $i$ have $B_i = i$.↵
↵
Thus, it remains to compute the number of ways to compute the number of sequences $B$ with at least $j$ equal positions. There are $\dbinom{N}{j}$ ways to choose $j$ positions where $B_i = i$. Then, it doesn't matter what we put in the remaining positions, so there are $\dbinom{M-j}{N-j}$ ways to choose the numbers and $(N-j)!$ ways to arrange them. Thus, the total number of ways to ensure that at least $j$ positions have $B_i = i$ is $\dbinom{N}{j} \dbinom{M-j}{N-j} (N-j)!$.↵
↵
By precomputing all relevant factorials and their modular inverses in $O(M)$, we can compute the above product in $O(1)$ for each $j$. We then sum these up using our PIE formula, giving us an $O(N+M)$ solution. Since $N \leq M$, this is simply $O(M)$.↵
↵
Time Complexity: $O(M)$. [Click here for my submission.](https://atcoder.jp/contests/abc172/submissions/14746808)↵
↵
---↵
↵
#F — Unfair Nim↵
↵
It is well known that the second player wins a game of Nim if and only if the bitwise XOR of the numbers of stones in each pile is equal to $0$. Thus, we want to make the equation $A_1 \wedge A_2 \wedge A_3 \wedge \cdots \wedge A_n = 0$. By taking the XOR of this equation with $A_3 \wedge A_4 \wedge \cdots \wedge A_n$, we have $A_1 \wedge A_2 = A_3 \wedge A_4 \wedge \cdots \wedge A_n.$ We can immediately compute the right-hand side, since it is fixed before we make our moves. Now, we want to find the largest $x$ between $1$ and $A_1$, inclusive, such that $x \wedge (A_1 + A_2 - x) = A_3 \wedge A_4 \wedge \cdots \wedge A_n.$↵
↵
We build $x$ via digit DP, determining the bits of $x$ from the most significant bit to the least significant bit. Let $a$ be the maximum possible value of $x$ thus far such that we have found a bit in which $x$ contains a $0$ while $A_1$ contains a $1$ (so, we know that no matter what bits we add to $a$ in the future, it will be less than $A_1$), or $-\infty$ if no such value exists thus far. Let $b$ be the value of $x$ such that thus far, all bits in $b$ are the same as those in $A_1$, or $-\infty$ if creating this value is impossible. Note that we cannot add a $1$ to $b$ if the corresponding bit in $A_1$ is a $0$, as this would make $b$ too large.↵
↵
Let $S = A_3 \wedge A_4 \wedge \cdots \wedge A_n.$ If $S$ contains a $0$ in any given bit, we know that $x$ and $A_1 + A_2 - x$ must either both contain a bit or neither must contain a bit. We can tell which case applies by determining whether after subtracting out all bits we've assigned so far, $A_1 + A_2$ is greater than $2^{k+1}$, where $k$ is the index of the current bit. This is because the sum of all future bits will be at most $2^{k+1} - 2$, so $A_1 + A_2 \geq 2^{k+1}$ both enables us to add two $1$s at position $b$ and forces us to do so. If we add a bit to both numbers, we add $2^k$ to $a$ and $b$, but set $b$ to $-\infty$ if $A_1$ contains a $0$ in position $k$. Otherwise, we don't add anything to either $a$ or $b$, but if $A_1$ contains a $1$ in position $k$, we can set $a$ to $\max(a, b)$, since now we've found a position in which $x < A_1$.↵
↵
If $S$ contains a $1$ in any given bit, we know that exactly one of $x$ and $A_1 + A_2 - x$ must contain a bit. Thus, we can add $2^k$ to $a$, because this will not make $a$ exceed $A_1$. If $A_1$ contains a $1$ in position $k$, we can also add $2^k$ to $b$, or we can alternatively assign a $0$ in order to guarantee that $x < A[1]$, allowing us to set $a$ to $\max(a, b)$. ↵
↵
At the end of this process, $a$ and $b$ are our possible values for $x$. Of course, if $a$ and $b$ are zero or $-\infty$, they can't work (the zero case fails because we cannot move every stone from the first pile). Moreover, we also must confirm that $a \wedge (A_1 + A_2 - a) = S$ in order to use $a$, and we must check the same equation for $b$. This is because the total bits we assign throughout our process may not equal $A_1 + A_2$, since the number of bits we assign is largely determined by $S$. (One countercase that demonstrates this issue is $N=3, A = 7, 5, 6$: our solution assigns one bit in position $2$, one bit in position $1$, and two bits in position $0$, but the total of these bits is $4 + 2 + 2 = 8 < 7+5.$) Then, we take the largest of these possible values for $x$ and subtract it from $A_1$ to get our answer.↵
↵
Time Complexity: $O(N + \log A_i).$ [Click here for my submission.](https://atcoder.jp/contests/abc172/submissions/14743239)↵
↵
---
