AtCoder-111A Simple Math 2
\(N\) 比较大，考虑倍增处理，设 \(f(N)=\left\lfloor\frac{10^N}{M}\right\rfloor\bmod M\)。
欲求 \(f(x+y)\)，利用 \(\left\lfloor\frac{ab}{c}\right\rfloor=\left\lfloor\frac{a}{c}\right\rfloor \times b+\left\lfloor\frac{(a\bmod c)\times b}{c}\right\rfloor\) 化简：
\[\begin{aligned}
f(x+y)&=\left\lfloor\dfrac{10^x\times 10^y}{M}\right\rfloor\bmod M\\
&=\left(\left\lfloor\dfrac{10^x}{M}\right\rfloor\times 10^y+\left\lfloor\dfrac{(10^x\bmod M)}\times 10^y{M}\right\rfloor\right)\bmod M\\
&=\left(\left\lfloor\dfrac{10^x}{M}\right\rfloor\times 10^y+\left\lfloor\dfrac{10^y}{M}\right\rfloor\times (10^x\bmod M)+\left\lfloor\dfrac{(10^x\bmod M)(10^y\bmod M)}{M}\right\rfloor\right)\bmod M
\end{aligned}
\]
只需要预处理 \(f(2^k)\) 以及 \(10^{2^k}\bmod M\) 即可。
提交记录：Submission - AtCoder
AtCoder-111B Reversible Cards
两种建模方法。
一种是 \(i\to a_i,i\to b_i\)，跑网络流。
另一种是 \((a_i,b_i)\)，对每个连通块分别考虑，类似省选 D2T2，如果是树一定只能选 \(|V|-1\) 个，否则 \(|V|\) 个都能选，证明考虑 Hall 定理。
提交记录：Submission - AtCoder
AtCoder-111C Too Heavy
一定是对每个置换环分别考虑。
除去恒等置换，要求 \(a_i>b_{p_i}\) 才有解。
观察发现，如果交换 \(i,p_i\)，那么相当于删去 \(p_i\)，\(i\) 与 \(p_{p_i}\) 直接相连，需要操作 \(|V|-1\) 次。
不妨选取 \(a_i\) 最大的 \(i\)，每次交换 \(i,p_i\) 并修改 \(p_i\) 为 \(p_{p_i}\)，由于所有 \(a_i>b_{p_i}\)，那么 \(a_i\) 一定可以一直交换，而 \(a_{p_i}\) 交换一次就合法了。
提交记录：Submission - AtCoder