AtCoder Regular Contest 116 解説

※今回はリアルタイム参戦していないため, 一部の内容を省略している.

##各問題ごとの詳細, 提出コード
|Question|After Contest|
|:--:|:--:|
|<font color=#808080> A問題 </font>|[■](https://atcoder.jp/contests/arc116/submissions/21500293)<br>$O(\log N)$<br>[■](https://atcoder.jp/contests/arc116/submissions/21517237)<br>$O(1)$|
|<font color=#008000> B問題 </font>|[■](https://atcoder.jp/contests/arc116/submissions/21500440)<br>(初AC)<br>[■](https://atcoder.jp/contests/arc116/submissions/21508282)<br>(解説に即した実装)|
|<font color=#00C0C0> C問題 </font>|[■](https://atcoder.jp/contests/arc116/submissions/21507596)|
|<font color=#0000FF> D問題 </font>|[■](https://atcoder.jp/contests/arc116/submissions/21507900)|
|<font color=#C0C000> E問題 </font>||
|<font color=#FF0000> F問題 </font>||

#今回の記事の注意
今回の記事に何回か出てくる記述についての説明をする. 整数 $m$ の素因数分解 $\displaystyle m=\prod_{p:{\rm Prime}} p^{e_p}$ の $e_p$ について, 有限個の素数 $p$ を除いて $e_p=0$ である. このことから, いくつかの式で無限和や無限積を考える所があるが, 実際には有限になっていることに注意せよ.

#問題ごとの略解
##<font color=#808080> A問題 (300pts, diff: 155) </font> [Odd vs Even](https://atcoder.jp/contests/arc116/tasks/arc116_a)
与えられた整数 $N$ に対して, $N$ は非負整数 $k$ と奇数 $M$ を用いて, $N=2^k M$ と表すことができる.

ここで, 一般論として, 整数 $n$ の素因数分解を $\displaystyle n=\prod_{q:{\rm Prime}} q^{e_q}$ したとき, 任意の素数 $q$ に対して, $0 \leq e'\_q \leq e_q$ ならば, $\displaystyle \prod_{q:{\rm Prime}} q^{e'_q}$ は $n$ の約数になっている.

$N$ の素因数分解を $\displaystyle N=2^e_2 \prod_{p:{\rm Odd~Prime}} p^{e_p}$ とする. このとき, 各奇素数 $p$ に対して $0 \leq e'\_p \leq e_p$ が成り立つとき, $\displaystyle \prod_{p:{\rm Odd~Prime}} p^{e'\_p}$ は $N$ の奇数の約数であり, 逆に全ての $N$ の奇素数はこのように書くことができる. よって, $N$ の奇約数の個数 $O$ は各奇素数 $p$ における $e'\_p$ の選び方から,
$$O=\prod_{p:{\rm Odd~Prime}} (1+e_p)$$
である.

次に偶約数について考える. 各奇約数 $r$ と $1 \leq e'\_2 \leq e_2$ を満たす任意の整数 $e'_2$ に対して, $2^{e'_2} \cdot r$ [^a1] は $N$ の約数になり, 逆に, 全ての $N$ の偶約数はこのように書くことができる. よって, $N$ の偶約数の個数 $E$ は $E=e_2 O$ である.

以上から, 奇約数の個数 $O$, 偶約数の個数 $E$ の間には $O=e_2 E$ という関係性があるので,
$$\begin{cases} 偶約数が多い & (e_2 \geq 2) \\\\
同じ & (e_2=1) \\\\
奇約数が多い & (e_2=0) \end{cases}$$
となる. 各 $N$ に対して $e_2$ は計算量 $O(\log N)$ で計算でき, 十分高速である.

ここで, この各条件は以下のように変形でき, 計算量を $O(1)$ にすることができる.
$$\begin{cases} 偶約数が多い & (N \pmod{4}=0) \\\\
同じ & (N \pmod{4}=2) \\\\
奇約数が多い & (N \pmod{4}=1,3) \end{cases}$$

[^a1]: $e'_2=0$ のときは奇約数になることに注意.

##<font color=#008000> B問題 (400pts, diff: 816) </font> [Products of Min-Max](https://atcoder.jp/contests/arc116/tasks/arc116_b)

$A$ を昇順にしてもよいことがわかる. 以下, $A_1 \leq \dots \leq A_N$ とする. このとき, 求めるべき値を以下のように変形する. ただし, 以下の変形において $\max$ を選ぶ際, 同じ値の項が複数ある場合, 添字が最も大きいものを選ぶことにする. 最小についても同様に, 添字が最も最小のものを選ぶことにする. また, 数列 $B \prec A$ で $B$ は $A$ の空でない部分列であることを表すとする. そして, 求めるべき値を $X$ とする.

```math
\begin{align*}
X
&=\sum_{B \prec A} (\max B)(\min B) \\\\
&=\sum_{i=1}^N \sum_{\substack{B \prec A \\\\ \max B=A_i}} (\max B)(\min B) \\
&=\sum_{i=1}^N \sum_{\substack{B \prec A \\\\ \max B=A_i}} A_i (\min B) \\
&=\sum_{i=1}^N A_k \left(\sum_{\substack{B \prec A \\\\ \max B=A_i}} \min B \right) \\
\end{align*}
```

以下, $\displaystyle Y_i:=\sum_{\substack{B \prec A \\\\ \max B=A_i}} \min B$ について, $\chi_{i,j}~(i \geq j)$ で $\max B=A_i, \min B=A_j$ をみたす部分列 $B$ の個数とする. すると, $\displaystyle Y_i=\sum_{j=1}^i \chi_{i,j} A_j$となる.

ここから, $\chi_{i,j}$ について考える. $\max B=A_i$ の条件下で,
$$\min B=A_j \iff B の中に A_1, \dots, A_{j-1} は現れず, A_j は現れる.$$
である. このとき, $A_{j+1}, \dots, A_{i-1}$ の選択は自由になることから,
$$\chi_{i,j}=2^{\max(0,(i-1)-(j+1)+1)}=\begin{cases}
2^{i-j-1} & (i>j) \\\\
1 & (i=j) \end{cases}$$
となる. よって,
$$Y_i=\sum_{j=1}^i \chi_{i,j} A_j=\sum_{j=1}^i \left(\begin{cases}
2^{i-j-1} & (i>j) \\\\
1 & (i=j) \end{cases} \right) A_j=\sum_{j=1}^{i-1} 2^{i-j-1} A_j+A_i$$
である. ここで,

```math
\begin{align*}
Y_{i+1}
&=\sum_{j=1}^i 2^{i-j} A_j+A_{i+1} \\\\
&=2\sum_{j=1}^{i-1} 2^{i-j-1} A_j+A_i+A_{i+1} \\\\
&=2(Y_i-A_i)+A_i+A_{i+1} \\\\
&=2Y_i-A_i+A_{i+1}
\end{align*}
```
である.

以上から,
$$X=\sum_{i=1}^N A_i Y_i,\quad Y_i=\begin{cases} A_1 & (i=1) \\\\ 2Y_{i-1}-A_{i-1}+A_i & (i \geq 2) \end{cases}$$
により求めることができる. 計算量は仮定したソートがボトルネックになり, $O(N \log N)$ である.
##<font color=#00C0C0> C問題 (500pts, diff: 1468) </font> [Multiple Sequences](https://atcoder.jp/contests/arc116/tasks/arc116_c)

末項の値で場合分けする. 以下, 末項が $x$ であるとする.

ここで, 長さ $N$ の<b>正</b>の実数列 $P=(P_i)\_{i=1}^N$ と, 以下で定義される<b>正</b>の実数列 $\widehat{P}=\left(\widehat{P}\_j \right)\_{j=1}^N$ は1対1対応である.
$$\widehat{P}\_1=P_1, \quad \widehat{P}\_2=\dfrac{P_2}{P_1}, \quad  \dots, \quad \widehat{P}\_N=\dfrac{P_N}{P_{N-1}} $$


以下, $A=(A_j)\_{j=1}^N$ に対して, $\widehat{A}=\left(\widehat{A}_j \right)\_{j=1}^N$ を考える. ここで, 今回与えられている条件はそれぞれ以下のようになる.

* $1 \leq A_i \leq M \iff 1 \leq \widehat{A}_1 \times \dots \times \widehat{A}_i \leq M$
* $A_{i+1}$ は $A_i$ の倍数 $\iff \widehat{A}_{i+1} \in \mathbb{Z}$

また, 末項が $x$ であるという条件から,

* 末項が $x \iff \widehat{A_1} \times \dots \times \widehat{A_N}=x$

となる. 以上から, 条件を満たし, 末項が $x$ になる長さ $N$ の数列の個数と, 長さ $N$ で総積が $x$ になる数列の個数は等しくなる.

以下, 長さ $N$ で総積が $x$ になる数列の個数を数える. $x$ の素因数分解を $\displaystyle x=\prod_{{\rm p:Prime}} p^{e^{(x)}\_p}$ とする. ここで, 各素因数ごとに独立に考えられる. このとき, 「$N$ 個の区別がつく箱に区別がつかないボール $e^{(x)}\_p$ 個を入れる場合の数は何通りか?」 という問題に帰着できる. この問題の答えは ${}\_N{\rm H}\_{e^{(x)}\_p}=\binom{N+e^{(x)}\_p-1}{e^{(x)}\_p}$ [^c1] である. 各素因数ごとに独立に素因数の担う場所を決定できるので, 長さ $N$ で総積が $x$ になる数列の個数 $T_x$ は
$$T_x=\prod_{p:{\rm Prime}} \binom{N+e^{(x)}_p-1}{e^{(x)}_p}$$
である.

最後に, 末項の可能性として, $1 \leq x \leq M$ となるので, 求めるべき答えは
$$\sum_{x=1}^M T_x=\sum_{x=1}^M \prod_{p:{\rm Prime}} \binom{N+e^{(x)}_p-1}{e^{(x)}_p}$$
である.

計算量は, $p=998244353$ として, $n! \pmod{p},(n!)^{-1} \pmod{p}$ を求めるのに $O(N+\log M+\log p)$ かかり, 総和を求める部分で素因数分解のパートで一般的な方法で $O(M\sqrt{M})$, Eratosthenes の篩を利用する方法で $O(M \log M)$ で求まる.

[^c1]: ${}\_n{\rm H}_r$ で重複組合せの個数を表す. 意味は本文の通り.


##<font color=#0000FF> D問題 (500pts, diff: 1718) </font> [I Wanna Win The Game](https://atcoder.jp/contests/arc116/tasks/arc116_d)

以下, $a~{\rm xor}~b$ を $a \oplus b$ と書くことにする. ここで, bitwise-xor は各 bit について独立であり, 他の bit に影響を与えないことに注意せよ.

また, この問題では各項の総和が $M$ であるとき, xor が $0$ になる組み合わせは何通りか? という問題なので, 形式的ベキ級数を用いた議論が非常に有用である.

第 $2^i$-bit について考える. まず, xor を $0$ にしなくてはならないので, $N$ 個の整数のうち, $2^i$-bit を立たせる個数は偶数個でなくてはならない. $N$ 個中 $2k$ 個の $2^i$-bitを立たせる方法は $\binom{N}{2k}$ 個であり, このとき数列の和として $k \cdot 2^{i+1}$ を消費する. この状況を表す形式的ベキ級数 $P_i$ は,
$$P_i(X)=\sum_{k=0}^\infty \dbinom{N}{2k} X^{k \cdot 2^{i+1}}$$

全ての非負整数 $i$ について考慮すると, この問題の答えを表す形式的ベキ級数 $Q$ は
$$Q=\prod_{i=0}^\infty P_i(X)=\prod_{i=0}^\infty \sum_{k=0}^\infty \dbinom{N}{2k} X^{k \cdot 2^{i+1}}$$
であり, $[X^M] Q$ が求めるべき答えである.

この形式的ベキ級数を求めるために, 愚直に畳み込みを行うと, $O(M^2 \log M)$ であり, 今回の問題ではこれでも通る. しかし, 数連変換 (NTT) を利用することにより, $O(M (\log M)^2)$ になり
, 更に, $P_i(X)$ が疎であることを利用すると,$O(M \log M)$ で実装できる. 二項係数の前計算も $O(\min (N,M))$ でできる.

##<font color=#C0C000> E問題 (800pts, diff: 2236) </font> [Spread of Information](https://atcoder.jp/contests/arc116/tasks/arc116_e)

(正解でき次第加筆予定)

##<font color=#FF0000> F問題 (800pts, diff: 3125) </font>[Deque Game](https://atcoder.jp/contests/arc116/tasks/arc116_f)

(正解でき次第加筆予定)