AtCoder ARC 134 C – The Majority
如此ruzhi的一道题目竟花去两小时有余，比赛结束也没写出来，实在惭愧。
拿到题目，很快想到一种DP：令$f(i, j, k)$表示“考虑到第$i$个盒子，第$1$种小球用去$j$个，第$2, 3, \dots, n$种小球用去$k$个”的方案数。容易转移。
然后发现$a_i$是$10^9$级别。同时题目告诉我们，相同类别小球无法区分，所以要是上述做法正确，为什么要分别给出$a_2, a_3, \dots$呢？如何在转移时确保每一种小球的使用次数正确？立刻想到正解与$\mathrm{O}(a_i)$基本无关。
由题意可知这是一个八连通的$2 \times n$网格。故我们扫描一遍，发现某列的两个格子均无法通过则失败。复杂度$\mathrm{O}(n)$。
或许是人品不错，最近两天接连刷到三道排列组合相关的题。在此作简单整理。
题意参见原题面。
很自然地想到，对于一个排列$P = (p_1, p_2, \dots, p_n)$，有$n$条$i \rightarrow p_i$的连边。因为排列中正整数$1, 2, \dots, n$恰好出现仅有一次，所以等价于每个点有且仅有一条出边、一条入边的图。容易发现这个图由若干个有向环构成（包括自环——即$p_i = i$的情况）。例如排列$P = (1, 3, 4, 2)$代表由$1 \rightarrow 1$和$2 \rightarrow 3 \rightarrow 4 \rightarrow 2$两个环组成的图。