A
逐位确定即可，不难计算方案数。
时间复杂度 \(\mathcal{O}(n^2)\) 或 \(\mathcal{O}(n)\)。
B
一眼但是很恶心的题。直接整除分块做做即可。
时间复杂度 \(\mathcal{O}(T \sqrt n)\)。
C
这场比赛最简单的题。
按照值从小往大考虑。设 \(f_{i, j}\) 表示考虑到 \(i\)，\(< i\) 的数一共换了 \(j\) 个 \(i\)，\(< i\) 的数的方案数。则状态总量为 \(\mathcal{O}(n \log n)\)，转移是前缀加，差分即可。
时间复杂度 \(\mathcal{O}(n \log n)\)。
D
若 \(k \nmid m\) 则答案为 \(0\)。以下令 \(m \leftarrow \frac{m}{k}\)。
众所周知，一个方案合法，则必然存在一种顺子和刻子的分配方案，使得从每个位置开始的顺子不超过 \(k\) 个。
先放顺子，设 \(f_i\) 表示一共放了 \(i\) 个顺子的方案数，容斥可得
\[f_i = \sum_j \binom{n - k + 1}{j} \binom{i - jk + n - k}{n - k} \]加上刻子，答案为
\[\sum_i f_i \binom{m - i + n - 1}{n - 1} \]如果要求 \(f\) 没有高效简单的做法。但是如果我们把两个式子写到一起，并把 \(j\) 提到最外层
\[\sum_j (-1)^j \binom{n - k + 1}{j} \sum_i \binom{i - jk + n - k}{n - k} \binom{m - i + n - 1}{n - 1} \]注意到 \(i\) 是没有范围限制的。根据恒等式
\[\sum_i \binom{a + i}{c} \binom{b - i}{d} = \binom{a + b + 1}{c + d + 1} \]可以得到答案为
\[\sum_j (-1)^j \binom{n - k + 1}{j} \sum_i \binom{m - jk + 2n - k}{2n - k} \]时间复杂度 \(\mathcal{O}(n^2)\)。
E
我们的目标是对于每个非叶子结点，都存在一条新加的边跨过它。
如果叶子个数为偶数，经典地，按照 \(\rm dfn\) 序分成两半，前一半匹配后一半即可。
如果叶子个数为奇数，我们需要选择一个的叶子连其他的点，剩下的叶子前后匹配。对于叶子 \(u\)，设 \(v\) 为 \(u\) 深度最小的祖先，满足 \(v \to u\) 的路径上除了 \(u, v\) 的其它点都只有一个儿子，则若选择 \(u\) 连其他的点，可以选的点为除了 \(v \to u\) 这条路径上的点外的任意点。枚举叶子贪心即可，不难证明正确性。需要注意的是，这时我们必须选定一个 \(\deg = 3\) 的结点作为根才能保证上述做法的正确性，显然 \(\deg = 3\) 的点在叶子个数为奇数的时候必然存在。
时间复杂度 \(\mathcal{O}(n \log n)\) 或 \(\mathcal{O}(n)\)。
F
看了 10min 就会了，但是因为前四题花了长达 100min 导致赛时没过 /cf
经典地，对于一个排列 \(p\) 和 \(i = 0, 1, \cdots, n\)，依次找出 \(p\) 中 \(\le i\) 的所有位置，这样会形成 \(n + 1\) 个 \(01\) 序列 \(s_0, \cdots, s_n\)。一种操作方案能将 \(p\) 排序当且仅当其能将 \(s_0, \cdots, s_n\) 排序。
称一个 \(01\) 序列是好的，当且仅当当前的操作能将其排序，则方案数就是 \(n\) 维空间中从 \((0, 0, \cdots, 0)\) 走到 \((1, 1, \cdots, 1)\)，每次只能向一个方向走一步，并且只能经过好的位置的路径数。
首先来考虑维护哪些 \(01\) 序列是好的。称操作 \(i\) 有效，当且仅当存在一个 \(01\) 序列 \(s\)，使得 \(s\) 经过前 \(i - 1\) 次操作后和经过前 \(i\) 次操作后不同。注意到共有 \(2^n\) 个序列，并且每个序列最多进行 \(n^2\) 次操作，所以有效操作的数量为 \(\mathcal{O}(n^2 2^n)\)。我们维护有效操作集合，如果当前操作有效，则更新其生效的每个 \(s\) 的状态，并判断其是否变为好的，并且更新有效操作集合。这一部分实现精细可以做到 \(\mathcal{O}(n^3 2^n)\)。
然后来考虑统计路径数。设 \(f_s\) 表示 \((0, 0, \cdots, 0) \to s\)，除了 \(s\) 以外都是好位置的路径数；\(g_s\) 表示 \(s \to (1, 1, \cdots, 1)\)，除了 \(s\) 以外都是好位置的路径数。加入一个好的序列 \(s\) 时，先用 \(f_s \times g_s\) 更新方案数，再更新 \(s\) 超集的 \(f\) 和子集的 \(g\) 即可。这一部分实现精细可以做到 \(\mathcal{O}(n 3^n)\)。
时间复杂度 \(\mathcal{O}(n^3 2^n + n 3^n)\)，但是实际上很跑不满。
标签：ARC160,sum,叶子,cdots,mathcal,binom,复杂度 From： https://www.cnblogs.com/Scintilla/p/17401478.html