线性筛

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

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日