Contest Info

date: 2018.11.01 19:35-00:35

practice link

Solutions

A. Twelve Months

题目大意：给你一副 \(1\sim n\) 各 \(4\) 张组成的扑克，将它们分成 \(n\) 堆，每堆 \(4\) 张。现在从第一堆开始，每次翻开顶上的那张牌，移动到该牌上所写的数字的那一堆，以此类推，直到移动到空堆为止。

现在告诉你最开始的 \(m\) 张被翻开的牌，等概率随机剩下的 \(n-m\) 张的所有可能的分法。求结束时每种局面的概率。一种局面是指：第 \(2\) 到第 \(n\) 堆中的每一堆是否被翻完（可以证明第 \(1\) 堆必然被翻完）。

题解：首先证明一定在第 \(1\) 堆结束：不妨设在第 \(i>1\) 堆结束，那么就要求第 \(i\) 堆翻开 \(4\) 张（即已有 \(4\) 张牌写有 \(i\)）后，还有一张牌为 \(i\)，矛盾。因此只能在第 \(1\) 堆结束。

那么问题转化为了：对于所有 \(\{4\cdot1,\cdots,4\cdot n\}\) 的排列（前 \(m\) 项已给出），在最后一个 \(1\) 之前出现 \(4\) 次的牌视为被翻完。问每种局面有多少种对应的排列。

设 \(dp[i][j][S]\) 表示前 \(i\) 个数值中有 \(j\) 张牌出现在最后一个 \(1\) 之前，被翻完的局面为 \(S\) 的方案数。根据组合数简单转移即可。

时间复杂度 \(\mathcal{O}(n^{2}2^{n})\)。