我是靠谱客的博主 潇洒彩虹,最近开发中收集的这篇文章主要介绍【错位+组合】排列计数,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

题目描述

求有多少种长度为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行,每行一个数,表示求出的序列数

 

样例输入

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

最后

以上就是潇洒彩虹为你收集整理的【错位+组合】排列计数的全部内容,希望文章能够帮你解决【错位+组合】排列计数所遇到的程序开发问题。

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

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(52)

评论列表共有 0 条评论

立即
投稿
返回
顶部