[Sdoi2016]排列计数

Excel数据排序：选中要排序的列，点击数据-排序，选择升序或降序，确定即可。 #生活知识# #生活经验# #软件#

问题 A: [Sdoi2016]排列计数

时间限制: 3 Sec  

内存限制: 512 MB

题目描述

求有多少种长度为 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

T掉的lucas p大时用lucas

#include<iostream>

#include<cmath>

#include<cstring>

#include<cstdio>

#include<queue>

#include<map>

#include<cstdlib>

#include<algorithm>

#define V 1000010

#define mod 1000000007

#define LL long long

using namespace std;

int n,m;

LL mb[V],md[V];

inline LL qp(LL x,LL y)

{

LL md=1;

while(y)

{

if(y&1)md=(LL)md*x%mod;

x=(LL)x*x%mod;

y>>=1;

}

return md;

}

inline LL get(int x,int y)

{

if(x<y)return 0;

if(y>x-y)y=x-y;

LL s1=1,s2=1;

for(int i=0;i<y;i++)

{

s1=(LL)s1*(x-i)%mod;

s2=(LL)s2*(i+1)%mod;

}

return s1*qp(s2,mod-2)%mod;

}

inline LL cc(int x,int y)

{

if(y==0)return 1;

return get(x%mod,y%mod)%mod;

}

inline int haha()

{

int t;

    LL x=1;

for(int i=2;i<=V-5;i++)

if(i%2)

    mb[i]=(mb[i-1]*i-1)%mod;

else

mb[i]=(mb[i-1]*i+1)%mod;

scanf("%d",&t);

while(t--)

    {

scanf("%d%d",&n,&m);

if(m>n)

  {

printf("0\n");

continue;

  }

if(m==0){

printf("%d\n",mb[n]);

continue;

  }

if(n==1||n==m)

  {

printf("1\n");

continue;

  }

printf("%lld\n",cc(n,m)*mb[n-m]%mod);

}

return 0; 

}

int gg=haha();

int main()

{;}

p小时直接用 阶乘

#include<iostream>

#include<cmath>

#include<cstring>

#include<cstdio>

#include<queue>

#include<map>

#include<cstdlib>

#include<algorithm>

#define V 1000010

#define mod 1000000007

#define LL long long

using namespace std;

int n,m;

LL mb[V],md1[V],md2[V];

inline LL qp(LL x,LL y)

{

LL md=1;

while(y)

{

if(y&1)md=(LL)md*x%mod;

x=(LL)x*x%mod;

y>>=1;

}

return md;

}

inline int haha()

{

int t;

LL x=1;

md1[0]=1;

md1[1]=md2[1]=1;

for(int i=2;i<=V-5;i++)

{

x*=i;x%=mod;

md1[i]=x;

md2[i]=qp(x,mod-2);

if(i%2)

mb[i]=(mb[i-1]*i-1)%mod;

else

mb[i]=(mb[i-1]*i+1)%mod;

}

scanf("%d",&t);

while(t--)

{

scanf("%d%d",&n,&m);

if(m>n)

{

printf("0$%^\n");

continue;

}

if(m==0){

printf("%d\n",mb[n]);

continue;

}

if(n==1||n==m)

{

printf("1\n");

continue;

}

printf("%lld\n",md1[n]%mod*md2[n-m]%mod*md2[m]%mod*mb[n-m]%mod);

}

return 0;

}

int gg=haha();

int main()

{;}

网址：[Sdoi2016]排列计数 https://www.yuejiaxmz.com/news/view/504230

相关内容

等差数列说课稿
斜床身数控车床厂家列举刀架常见故障原因及排除方法
抽屉原理与排列组合
数列求和数列的通项是n的4次方，求其前n项和，不用数学归纳法 爱问知识人
数列{an}、{bn}分别为等比数列与等差数列，a1=b1=1．则b2≥a2...
关于斐波那契数列 组合错排问题和一些递推公式合集整理
蔡司智锐数码型系列
数据结构之循环队列
已知数列{bn}中，b1＝117，bn1bn=bn2．数列{an? 爱问知识人
下面几个数列}中，}不收的数列是〔. 1.11. Aa,=。(

随便看看