概述
题目描述
求有多少种长度为n的序列A,满足以下条件:
1~n这n个数在序列中各出现了一次
若第i个数A[i]的值为i,则称i是稳定的。序列恰好有m个数是稳定的满足条件的序列可能很多,序列数对10^9+7取模。
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、m。
T=500000,n≤1000000,m≤1000000
输出
输出T行,每行一个数,表示求出的序列数
样例输入
5
1 0
1 1
5 2
100 50
10000 5000
样例输出
0 1 20 578028887 60695423
有m个位置的数要等于i,其他n-m个位置腰错位,用f[i]=(i+1)*(f[i-1]*f[i-2])推一下,最后c(n,m)*f[n-m]就行了
#include <bits/stdc++.h> #define ll long long using namespace std; const ll mod=1e9+7; ll t,n,m; ll f[5000005],fac[5000005],inv[5000005]; void init() { ll N=2000000; f[0]=1,f[1]=0,f[2]=1,fac[0]=1,inv[0]=inv[1]=1; for(ll i=3;i<=N;i++) f[i]=(i-1)*((f[i-1]+f[i-2])%mod)%mod; for(ll i=1;i<=N;i++) fac[i]=fac[i-1]*i%mod; for(ll i=2;i<=N;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod; for(ll i=1;i<=N;i++) inv[i]=inv[i]*inv[i-1]%mod; } ll c(ll n,ll m) { /*if(!n&&!m) return 0;*/ if(n<m) return 0; return fac[n]*inv[m]%mod*inv[n-m]%mod; } int main() { init(); scanf("%lld",&t); while(t--) { scanf("%lld %lld",&n,&m); printf("%lldn",c(n,m)*f[n-m]%mod); } return 0; }
转载于:https://www.cnblogs.com/Diliiiii/p/9416204.html
最后
以上就是潇洒彩虹为你收集整理的【错位+组合】排列计数的全部内容,希望文章能够帮你解决【错位+组合】排列计数所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复