AtCoder 做题记录

AtCoder Regular Contest 186

A mod M Game 2

Difficulty：1042

唐完了，不会做

打表（大便）题， $1 \le\frac{n\times(n-1)}2 \mod m \le n$ 时 Bob，否则 Alice。

B +1 and -1

Difficulty：1332

我都能场

最后数列的状态固定，从前往后模拟，前面有多的就留个 tag。

E Adjacent GCD

Difficulty：2185

欧拉函数，数论

欧拉函数反演

n=\sum_{d|n} \varphi(d) \\ \gcd(a,b)=\sum_{d|\gcd(a,b)} \varphi(d) = \sum_{d|a \and d|b} \varphi(d)

对于本题，每次加入一个 $a_i$ 后，新增 $ans+\sum_{j=1}^{i-1} \gcd(a_j,a_i)\times2^{j-1}$ 的贡献。

由于 $\gcd$ 的其中一项确定，则可以枚举 $a_i$ 的因数 $d$ ，添加 $sum_d \times \varphi(d)$ 的贡献。最后对于每个因数 $d$ ， $sum_d +=2^{i-1}$ 即可。

D Random Walk on Tree

Difficulty：2649

推式子，期望

就是走完 $n$ 条长度为 $m$ 的链。走完一条链的充要条件是走到叶子节点，钦定 $dep_0=0$ 。定义有效点为之前没别走过的点。

$f_i$ 表示从深度为 $i$ 的有效点走到 $i+1$ 的有效点期望步数。

f_{i}=\frac12+\frac{1+f_{i-1}+f_{i}}2 \\ f_i=2+f_{i-1}

即有 $\frac12$ 的概率直接走到，和先往 $i-1$ 走再走回来，再到 $i+1$ 的步数期望。

初始化 $f_0$ 与当前有多少条已经走完的链相关，并且如果走到了无效点还要走回来。设可以走到的有效点数为 $k$ ， $p_i$ 表示从深度为 $i$ 的点走到 $i-1$ 的步数期望。

$p$ 实际上在链上走的情况和 $f$ 相同，故 $p_i=2+p_{i+1}$ ，初始化 $p_m=1$ 。

f_0=\frac{k}{n}+(1-\frac{k}{n})\times(1+p_1+f_0) \\ f_0=\frac{n+(n-k)\times p_1}i

先计算从 $n-1$ 个叶子回到 $0$ 号点的贡献，即为 $(n-1)\times\sum_{i=1}^mp_i$ 。

再计算从 $0$ 号点到 $dep=1$ 的有效点后再到叶子节点的贡献和，即为 $\sum_{i=1}^n\sum_{j=1}^mf_j$ ，时间复杂度为 $O(n^2)$ （注：每次 $f_j$ 都需要重新计算，因为 $f_0$ 的值会变）。

观察到 $f_i=2+f_{i-1}$ 的式子非常简单，甚至是等差数列，可以得到通项公式 $f_i=f_0+2\times(i-1)$ ，故

\sum_{i=1}^m f_i=\sum_{i=1}^m(f_0+2\times(i-1))=m\times f_0 +m \times (m-1)

优化后就可以 $O(1)$ 求出 $f_0$ 和 $\sum f_i$ 了，复杂度为 $O(n \log_2n)$ ，使用预处理逆元做到 $O(n)$ ~~，但是我懒了~~。

Code

p[m]=1;
for(int i=m-1;i;i--)  p[i]=imadd(p[i+1],2);
int invn=qpow(n,mod-2);
int ans=0,sum=0;
for(int i=1;i<=m;i++)   madd(ans,p[i]);
mmul(ans,n-1);
for(int i=1;i<=n;i++){
    int f0=immul(imadd(n,immul(n-i,p[1])),qpow(i,mod-2));
    madd(ans,immul(m,f0));
    madd(ans,immul(m,m-1));
}

AtCoder Regular Contest 186

B Typical Permutation Descriptor

Difficulty：1677

赛时差一点写完的计数，唐

不难得出当前序列中 $p$ 最小的数的位置，然后从这一点断开后形成两个新区间，两个区间相互独立，只要 $\times \binom{r-l}{p-l}$ 将数划分到两个区间即可。

C Ball and Box

Difficulty：2451

贪心，博弈

按容量从小到大排序，相同容量花费从大到小。

最后的状态一定形如 $V_i$ 最大的 $m-1$ 个会只获得 $1$ 的贡献，剩余获得 $V_i$ 的贡献，即 $s=\sum_{i=1}^{k-m+1}V_i+m-1-\sum_{i=1}^kP_i$ 。

对后缀用大根堆维护最小的 $m-1$ 个 $V_i$ 作为所选的数中最大的 $m-1$ 个，剩余的选取所有 $[1,i-1]$ 中 $(V_i-P_i)$ 为正的，求和即可。

A Underclued

Difficulty：2511

性质，转化

好困难。

看到 01 矩阵，尝试给二分图定向。当 $a_{i,j}=0$ 时， $L_i \leftrightarrow R_j$ ，当 $a_{i,j}=1$ 时， $R_i \leftrightarrow L_j$ ，则两个矩阵相似即为对于每个点在两个图中的出入度相同。

原矩阵上 $(i,j)$ 是不动点，当且仅当在二分图中改变图的形态但出入度不变时，上面连的边不变。考虑变一条边的方向后，会继续影响别的点，知道绕回原点，即形成一个简单环后才会结束，则不动点即为二分图上不在简单环上的边。

转化后就不困难了，设 $dp_{i,j,k}$ 表示左部点前 $i$ 个点和右部点前 $j$ 个点，形成的环能否覆盖恰好 $k$ 条边。枚举左部点新加 $u$ 个点，右部点新加 $v$ 个点，且这些点形成一个强连通分量。新覆盖成了 $u\times v$ 条边，即 $u$ 个左部点都会和 $v$ 个右部点的连边一一被覆盖。因为是可行性 dp，转移可以用 bitset，时间复杂度降为 $\mathcal O(\frac{n^6}\omega)$ ，但不用也能过。

AtCoder Regular Contest 187

D Many Easy Optimizations

Difficulty：2880

here

AtCoder Regular Contest 192 (Div. 2)

好像已经很久没写过了 arc 了。但这场也是赛后的。

A ARC Arc

Difficulty：1387

结论

结论题。手玩一下发现 ARCR ARCR ARCR 这种结构可以将全部都赋值成 1，所以 $4|n$ 的都是 Yes，其余的全 0 情况都是 No。

当 $n$ 为奇数时，只要 A 中有 $1$ 个 1 就是 yes。偶数时每次操作肯定是将一组 $i$ 为奇数和偶数的 $A_i$ 和 $A_{i+1}$ 从 1 变为 0，所以初始时 $A_i=1$ 的 $i$ 至少在奇数位和偶数位都有一个，发现可以构造。

B Fennec VS. Snuke 2

Difficulty：1783

结论，博弈

前两题都是结论，真的受不了一点。

当有多堆被操作过后，可以直接合并成一堆。最后先取到只剩两堆时谁是胜者。

普遍考虑 $N=3$ 的情况，若有奇数堆，先手则先操作奇数堆，最后还是先手胜。

由于最后剩余的两堆肯定是只各被取了 $1$ 次，其它堆都被取完，所以剩余两堆和的奇偶性直接决定了胜败方。

删除奇数个就是先手胜，偶数个就是后手胜。

若 $2|\sum A$ ，只需后手和先手取相同奇偶性的堆即可，因为 $A$ 的和为偶数，所以有偶数个奇数堆，这样一定能取到剩下两堆的奇偶性相同。

否则先手先随便取，然后变成后手，操作同上。

C Range Sums 2

交互，模拟

感觉前三道题都比较无聊，都比较抽象。

先用 $1$ 跑 $n-1$ 遍，找到距离 $1$ 最远的点 $x$ ，再通过 ask(2,x) 看 $p_x=1$ 还是 $p_x=n$ 。接着用 $x$ 再问 $n-2$ 遍，就能得到除了 $x$ 和与 $x$ 相邻的节点外的所有信息，再问一遍与 $x$ 距离为 $2$ 的点就做完了，实现有点绕，操作次数 $2n-1$ ，复杂度 $O(n)$ 。