[洛谷P4071][SDOI2016]排列计数

题目

题目描述

求有多少种长度为 n 的序列 A,满足以下条件:
1 ~ n 这 n 个数在序列中各出现了一次
若第 i 个数 A[i] 的值为 i,则称 i 是稳定的。序列恰好有 m 个数是稳定的
满足条件的序列可能很多,序列数对 10^9+7 取模。

输入格式

第一行一个数 T,表示有 T 组数据。
接下来 T 行,每行两个整数 n、m。
T=500000,n≤1000000,m≤1000000

输出格式

输出 T 行,每行一个数,表示求出的序列数

输入样例

输出样例

题解

没思路?我们来找规律!
比如一个\(n=5\)的排列,我们假设\(m=2\)也就是说,我们其实已经确定了排列种某些位置的值,就这个例子来说:

\(12???\) \(1?3??\) \(1??4?\) \(1???5\) \(?23??\) \(?2?4?\) \(?2??5\) \(??34?\) \(??3?5\) \(???45\)

共10种,很容易发现其实就是\(C_n^m\),那么其中的问号又多少种排列呢?

没思路?我们再来找规律!
我们设\(D_i\)为i个?的可能的排列数,显然,\(D_1=0\) \(D_2=1\)
接着我们来看下\(D_3\),可以有\(312\),\(231\)
如果我们继续找下去的话,容易出错,所以我们现在来找找规律(灵魂画师)。
就拿\(D_4\)来说,上面的是数,下面的是位置,首先,1不能放到1号位,而且放到2,3,4上对于递推是等价的,于是他别无选择地放到了其他地方(假设是2号位)

然后我们假设2放到1号位上去,剩下的3,4正好是\(D_2\)

但2怎么可能只有放在1号位上的命运呢?它还可以不放到1号位,咦?我们之前说,i不能放到i号位,那么既然2不放到1号位,那么1号位在这里是不是等价于2号位呢?没错!

而之前的“万恶之源”数字1,它有\(n-1\)种放法,所以我们就大胆猜测:\(D_n=(n-1)(D_{n-1}+D_{n-2})\)
严谨的证明还请大家自己百度
然后我们就愉快地输出\(C_n^m\times D_{n-m}\)就好啦
其他知识点比如说逆元求组合数(费马小定理)还请大家自行了解

代码

发表评论

电子邮件地址不会被公开。 必填项已用*标注