洛谷-4071 [SDOI2016]排列计数

题目描述
求有多少种长度为 n 的序列 A，满足以下条件：
1 ~ n 这 n 个数在序列中各出现了一次
若第 i 个数 A[i] 的值为 i，则称 i 是稳定的。序列恰好有 m 个数是稳定的
满足条件的序列可能很多，序列数对 $10^9+7$ 取模。
输入格式
第一行一个数 T，表示有 T 组数据。
接下来 T 行，每行两个整数 n、m。
输出格式
输出 T 行，每行一个数，表示求出的序列数

输入输出样例
输入
5
1 0
1 1
5 2
100 50
10000 5000

输出
0
1
20
578028887
60695423

说明/提示
T=500000 ，n≤1000000 ，m≤1000000 。

解释：答案=$C_n^m\ast D(n-m)$其中$D$为错排公式，$D(n)=(n-1)\ast (D(n-1)+D(n-2))$再利用逆元就OK

#include<iostream>
#define mod 1000000007
#define N 1000003
using namespace std;
int T=0;
int n=0,m=0;
long long D[N]={1,0,1};
long long fact[N]={1};
long long inv[N]={0,1};
long long pow(long long a,long long b){
    long long ret=1;
    while(b){
        if(b&1) ret=ret*a%mod;
        a=a*a%mod;b>>=1;
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(false);
    for(int i=1;i<N;i++) fact[i]=fact[i-1]*i%mod;
    for(int i=3;i<N;i++) D[i]=(i-1)*((D[i-1]+D[i-2])%mod)%mod;
    for(int i=0;i<N;i++) inv[i]=pow(fact[i],mod-2);
    cin>>T;
    while(T--){
        cin>>n>>m;
        long long ret1=fact[n]*D[n-m]%mod;
        long long ret2=inv[m]*inv[n-m]%mod;
        cout<<ret1*ret2%mod<<endl;
    }
    return 0;
}

最后

以上就是专注夏天为你收集整理的洛谷-4071 [SDOI2016]排列计数的全部内容，希望文章能够帮你解决洛谷-4071 [SDOI2016]排列计数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。