题目描述
求有多少种长度为 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 行，每行一个数，表示求出的序列数
样例输入
51 01 15 2100 5010000 5000
样例输出
012057802888760695423 题解 这个数据范围，除了有公式否则怎么都过不了……然后开始推公式，这是个排列组合的问题吧，然后推推推，本来是手写了几种情况的，但是后来觉得可能不够准确就弃了。坚持从纯数学意义上推公式，然而有种悲剧叫数学能力不够，最终这题完全没有想到怎么做。据说是高考难度的数学题，但是我高考还没学到这，一年前夏令营陶陶讲的又差不多忘干净了QAQ。数学问题只能用数学方法拿分，这话相当有道理…… n个数里m个稳定，这一步用组合是毋庸置疑，随便预处理一下阶乘+乘法逆元就好。n-m个不稳定的是我在考场上没有想到解决办法的地方，整的式子推不出来，分类讨论又太过繁琐。然而这个错排是有公式的：f[n]=(n-1)*(f[n-1]+f[n-2])。第n个物品有n-1个位置可选，假设选定了k位置，考虑k的选择分两种，不选n和选n。不选n的情况，将n看作k，即k不能选择自身，转化为f[n-1]；选N的情况即f[n-2]。
#include#include #include #include #define ll long longusing namespace std;const int mod=1000000007;const int sj=1000010;int ca,n,m;ll jc[sj],f[sj],ans;ll e_gcd(ll n,ll m,ll &x,ll &y){ if(m==0) { x=1,y=0; return n; } ll an=e_gcd(m,n%m,x,y); ll t=x; x=y; y=t-n/m*y; return an;}ll ny(ll a,ll c){ ll x,y; ll gcd=e_gcd(a,c,x,y); x*=1/gcd; c/=gcd; if(c<0) c=-c; ll jg=x%c; if(jg<0) jg+=c; return jg;}int main(){ scanf("%d",&ca); jc[0]=jc[1]=1; for(int i=2;i<=sj-10;i++) jc[i]=(jc[i-1]*i)%mod; f[1]=0,f[0]=1; for(int i=2;i<=sj-10;i++) f[i]=((i-1)*(f[i-1]+f[i-2]))%mod; for(int l=1;l<=ca;l++) { scanf("%d%d",&n,&m); ans=(((jc[n]*ny(jc[m],mod))%mod)*ny(jc[n-m],mod))%mod; ans=(ans*f[n-m])%mod; printf("%lld\n",ans); } return 0;}