排列组合

AtCoder ARC 134 C – The Majority

如此ruzhi的一道题目竟花去两小时有余,比赛结束也没写出来,实在惭愧。

拿到题目,很快想到一种DP:令f(i,j,k)f(i, j, k)表示“考虑到第ii个盒子,第11种小球用去jj个,第2,3,,n2, 3, \dots, n种小球用去kk个”的方案数。容易转移

然后发现aia_i10910^9级别。同时题目告诉我们,相同类别小球无法区分,所以要是上述做法正确,为什么要分别给出a2,a3,a_2, a_3, \dots呢?如何在转移时确保每一种小球的使用次数正确?立刻想到正解O(ai)\mathrm{O}(a_i)基本无关。

(更多…)

More
  • 2022年1月30日

或许是人品不错,最近两天接连刷到三道排列组合相关的题。在此作简单整理。

AtCoder ABC226 F – Score of Permutations

题意参见原题面。

很自然地想到,对于一个排列P=(p1,p2,,pn)P = (p_1, p_2, \dots, p_n),有nnipii \rightarrow p_i的连边。因为排列中正整数1,2,,n1, 2, \dots, n恰好出现仅有一次,所以等价于每个点有且仅有一条出边一条入边的图。容易发现这个图由若干个有向环构成(包括自环——即pi=ip_i = i的情况)。例如排列P=(1,3,4,2)P = (1, 3, 4, 2)代表由111 \rightarrow 123422 \rightarrow 3 \rightarrow 4 \rightarrow 2两个环组成的图。

(更多…)

More
  • 2021年11月14日