Luogu – P3214 – [HNOI2011]卡农

题解

思路

$n$ 个音,$m$ 个片段。

题目忽略顺序,我们忽略要求,最后用答案 $\times \frac{1}{m!}$ 即可。

利用二进制转化一下:

每种选择方式编号为 $1,2,\cdots, 2^n-1$。选 $m$ 个数,异或和为 $0$,且不存在两个相同。

先不考虑任意两个数不相同:

前 $i$ 个数的可选方案数,不是 $C_{2^n-1}^i$,因为需要保证异或和为 $0$。

注意到,若前 $i-1$ 个数已经确定,那么第 $i$ 个数则唯一固定,所以方案数为 $C_{2^n-1}^{i-1}$.

但这并不完全正确,有两种不合法的情况需要考虑:

情况一

若前 $i-1$ 个数异或和为 $0$,第 $i$ 个数只能为 $0$,但可选数中不存在 $0$ 这个数。

这种情况的方案数为 $f_{i-1}$.

情况二

根据组合数,我们选取的前 $i-1$ 个数一定两两不等,但第 $i$ 个数有可能和前面中的某个数相等,需要减去这种情况。

不妨设第 $j$ 个数与第 $i$ 个数相等。

  1. 其他 $i-2$ 个数异或和为 $0$、且选取方式完全合法,有 $f_{i-2}$ 种选择方法。
  1. $j$ 这个位置有 $(i-1)$ 种可能,每个位置下,都可以从 $1\sim 2^n-1$ 中选取,唯一的限制是不能与其他 $(i-2)$ 个数相等,有 $(i-1)[2^n-1-(i-2)]$ 种选择方法。

综上,第二组不合法情况的方案数为 $f_{i-2}(i-1)[2^n-1-(i-2)]$.

将这两种情况减去即可。

设 $f_i$ 表示前 $i$ 个片段的可选方案数。

$$
f_i=C_{2^n-1}^{i-1}-f_{i-1}-f_{i-2}(i-1)(2^n-1-(i-2))
$$

递推求解,

$$
\operatorname{Ans}=\frac{f_m}{m!}\bmod 100000007
$$
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇