Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


  1. 「SCOI2009」游戏 - 群论 + 背包 DP

    windy 学会了一种游戏。对于 1 1 N N N N 个数字,都有唯一且不同的 1 1 N N 的数字与之对应。最开始 windy 把数字按顺序 1,2,3,,N 1, 2, 3, \ldots, N 写一排在纸上。然后再在这一排下面写上它们对应的数字。然后又在新的一排下面写上它们对应的数字。如此反复,直到序列再次变为 1,2,3,,N 1, 2, 3, \ldots, N

    如:1,2,3,4,5,6 1, 2, 3, 4, 5, 6 对应的关系为

    {122331455466 \begin{cases} 1 \rightarrow 2 \\ 2 \rightarrow 3 \\ 3 \rightarrow 1 \\ 4 \rightarrow 5 \\ 5 \rightarrow 4 \\ 6 \rightarrow 6 \end{cases}

    windy 的操作如下:

    这时,我们就有若干排 1 1 N N 的排列,上例中有 7 7 排。现在 windy 想知道,对于所有可能的对应关系,有多少种可能的排数。

    于  BZOJ, DP, SCOI, 数学, 群论, 背包 DP 继续阅读

  2. 「HNOI2008」Cards - Burnside 引理

    n n 张牌,3 种颜色,和 m m 种洗牌方案,求本质不同的染色方案数。

    于  BZOJ, Burnside 引理, HNOI, 数学, 群论 继续阅读