RainAir
My OI Blog
RainAir
ARC093F - Dark Horse

题意

有 $2^N$ 个人打锦标赛,他们的过程是随机一个排列,然后按照这个排列站好。每轮是第 $2_i − 1$ 个人和第 $2_i$ 的人比赛,败者淘汰。 你是 $1$ 号选手,你碰到$A_1,A_2,\cdots,A_m$ 会输,碰到剩下的会赢。如果比赛和你无关,那么编号小的赢。
求有多少个排列,能够使你最后赢。答案对 $10^9 + 7$ 取模。 $1\leq N\leq 16,0\leq M\leq 16,2\leq A_i \leq 2^N$。

题解

对于 $N \leq 4$ 我们可以使用 sb 状压过掉(这也导致了我的思维定式)。
其实这个题也算是套路。首先我们考虑决定一个排列是否胜利的条件是啥:发现将这个排列分成 $N$ 段,第 $i$ 段是 $[2^i,2^{i+1}-1]$。如果这个排列会让 $1$ 胜利当且仅当每一段的编号最小的选手都不能打败 $1$。
那么我们就容斥吧(悲)限制变成了某些区间的最小值是能打败 $1$ 的,其他区间随便填。
设 $f_{i,S}$ 表示从高到低考虑了前 $i$ 个数,$S$ 区间的最小值已经是能打败 $1$ 的人了的方案数。转移枚举这个人被放在了哪个区间即可:算出比这个人大且没用过的人的个数,组合数算一下就可以了(别忘了这是排列)
我们上面的计算是钦定了 $1$ 在 $1$ 位置的,注意到 $1$ 在其他的位置其实也是和这种情况等价的,所以答案要乘上个 $2^n$。

代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/909
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

ARC093F - Dark Horse
题意 有 $2^N$ 个人打锦标赛,他们的过程是随机一个排列,然后按照这个排列站好。每轮是第 $2_i − 1$ 个人和第 $2_i$ 的人比赛,败者淘汰。 你是 $1$ 号选手,你碰到$A_1,A_2,\cdots,A_m…
扫描二维码继续阅读
2019-10-18
标签
近期评论