Luogu – P4071 – [SDOI2016]排列计数

题目信息

难度:提高+/省选-
算法:数学递推、逆元

题目描述

求有多少种 $1$ 到 $n$ 的排列 $a$,满足序列恰好有 $m$ 个位置 $i$,使得 $a_i=i$.

答案对 $10^9+7$ 取模,多组询问,询问次数为 $T$.

测试点编号$T=$$n, m\leq$测试点编号$T=$$n, m\leq$
$1 \sim 3$$10^3$$8$$10 \sim 12$$10^3$$10^3$
$4 \sim 6$$10^3$$12$$13 \sim 14$$5\times 10^5$$10^3$
$7 \sim 9$$10^3$$100$$15 \sim 20$$5\times 10^5$$10^6$

对于 $100\%$ 的数据,$0\leq m\leq 10^6$.

$\rm{Subtask}$ $\rm{1}$

$T=10^3$,$n, m\leq 8$.

对于每次询问,暴力枚举所有排列,时间复杂度 $\mathcal{O}(T\times n!)$,期望得分 $\rm{15pts}$.

$\rm{Subtask}$ $\rm{2}$

想到错排之后,正解非常自然。

根据小学排列组合知识,我们从数列中任意取 $n$ 个数,让它们满足 $a_i=i$,情况数为 $C_{n}^{m}$.

又因为 $n$ 个数的排列中,有 $m$ 个位置满足 $a_i=i$,对于剩下的 $n-m$ 个位置需要满足 $a_i\neq i$.

这样的情况数是 $n-m$ 的错排数,也就是 $D_{n-m}$.

由于乘法原理,最终的答案就是 $C_{n}^m\times D_{n-m}$.

对于多组询问,我们需要 $\mathcal{O}(n)$ 预处理组合数和错排数。

暂无评论

发送评论 编辑评论

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