错排问题

错排公式

d[n]=(n-1)*(d[n-1]+d[n-2])

模版题：

lgP1595 信封问题

题目描述

某人写了n封信和n个信封，如果所有的信都装错了信封。求所有信都装错信封共有多少种不同情况。

输入格式

一个信封数n（n<=20）

输出格式

一个整数，代表有多少种情况。

输入输出样例
输入 #1
2
输出 #1
1
输入 #2
3
输出 #2
2


    第一次估计错误 喜提60
（话说字体为什么变了鸭）
   
  long long long is too long for  GCC
  
   代码如下

 1 #include<bits/stdc++.h>
 2 #define re register int
 3 #define LL long long 
 4 #define maxn 20+5 
 5 
 6 using namespace std;
 7 int n; 
 8 LL d[maxn]; 
 9 int main()
10 {
11     ios::sync_with_stdio(false);
12     cin>>n;
13     d[2]=1;
14     for(re i=3;i<=n;i++)
15     d[i]=(i-1)*(d[i-1]+d[i-2]);
16     cout<<d[n];
17  }

View Code

UVA11481 Arrange the Numbers

愉快地复制在luogu写的题解（题解这东西没必要写两遍嘛）

前置知识：错排公式（好吧知不知道错排公式不是很重要）

题意：

给出n,m,k,求n个数的排列满足前m个数中恰好有k个数不是错排的方案数。

多组输入输出，数据组数t满足：1<=t<=5.

m个数钦定k个数在正确的位置上的方案数是： $C_{m}^{k}$

因为要求恰好k个数不是错排，那么剩下n-k个数中前m-k个数必定是错排。

设f[i][j]为i个数，前j个数必须是错排的方案数。

则f[i][0]=i!

f[i][j]=f[i][j-1]-f[i-1][j-1]

i个数前j个必为错排的方案数==i个数前j-1个数必为错排的方案数-i个数前j-1个数必为错排&&第j个数是j的方案数

因为第j个数已经钦定 所以(i个数前j-1个数必为错排的方案数&&第j个数==j的方案数)==i-1个数前j-1个数必为错排的方案数

细节见代码

 1 #include<bits/stdc++.h>
 2 #define re register int
 3 #define maxn 1000+5
 4 #define LL long long
 5 #define mod 1000000007
 6 
 7 using namespace std;
 8 int t,n,m,k;
 9 LL c[maxn][maxn];
10 LL f[maxn][maxn];//f[i][j]表示i位数前j位错排的方案数 
11 void pre()
12 {
13     for(re i=0;i<=1000;i++)
14     c[i][0]=1;//c[0][0]也设1 不然乘的时候会爆炸233333 
15     for(re i=1;i<=1000;i++)
16     for(re j=1;j<=i;j++)
17     c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
18     f[0][0]=1;//不初始化成1 f[1][1]&&f[1][0]会出错
19     //当然f[1][1]会出错比较重要 
20     for(re i=1;i<=1000;i++)
21     f[i][0]=(f[i-1][0]*i)%mod;
22     for(re i=1;i<=1000;i++)
23     for(re j=1;j<=i;j++)
24     f[i][j]=((f[i][j-1]-f[i-1][j-1])%mod+mod)%mod;
25     //i个数前j个必为错排的方案数==i个数前j-1个数必为错排的方案数-i个数前j-1个数必为错排&&第j个数是j的方案数
26 
27     //因为第j个数已经钦定 所以(i个数前j-1个数必为错排的方案数&&第j个数==j的方案数)==i-1个数前j-1个数必为错排的方案数 
28 }
29 int main()
30 {
31     ios::sync_with_stdio(false);
32     cin>>t;
33     pre();
34     for(re i=1;i<=t;i++) 
35     {
36         cin>>n>>m>>k;
37         LL  ans=(c[m][k]*f[n-k][m-k])%mod;
38         cout<<"Case"<<" "<<i<<": "<<ans<<endl; 
39     }
40     return 0;
41 }

View Code

P4071 [SDOI2016]排列计数

题目描述

求有多少种长度为 n 的序列 A，满足以下条件：

1 ~ n 这 n 个数在序列中各出现了一次

若第 i 个数 A[i] 的值为 i，则称 i 是稳定的。序列恰好有 m 个数是稳定的

满足条件的序列可能很多，序列数对 $10^9+7 取模。$

输入格式

第一行一个数 T，表示有 T 组数据。

接下来 T 行，每行两个整数 n、m。

输出格式

输出 T 行，每行一个数，表示求出的序列数

输入输出样例
输入 #1
5
1 0
1 1
5 2
100 50
10000 5000
输出 #1
0
1
20
578028887
60695423
说明/提示

测试点 1 ~ 3：

测试点 4 ~ 6：

测试点 7 ~ 9：

测试点 10 ~ 12：

测试点 13 ~ 14：

测试点 15 ~ 20：

$答案即为$C_{n}^{m}$*d[n-m]$

 1 #include<bits/stdc++.h> 
 2 #define re register int 
 3 #define LL long long 
 4 #define mod 1000000007
 5 #define maxn 1000000+5
 6 
 7 using namespace std;
 8 LL fac[maxn],inf[maxn],d[maxn];
 9 LL qpow(LL a,LL b)
10 {
11     LL res=1;
12     while(b)
13     {
14     if(b&1) res=(res*a)%mod;
15     a=(a*a)%mod;
16     b>>=1;
17     }
18     return res;
19 }
20 void pre()
21 {
22     fac[1]=1;
23     inf[1]=1;
24     for(re i=2;i<=1000000;i++)
25     {
26         fac[i]=(fac[i-1]*i)%mod;
27         inf[i]=qpow(fac[i],mod-2)%mod;
28     }
29     d[1]=0,d[2]=1;
30     for(re i=3;i<=1000000;i++)
31     d[i]=(i-1)*(d[i-1]+d[i-2])%mod;
32 }
33 int t,n,m;
34 int main()
35 {
36     ios::sync_with_stdio(false);
37     cin>>t;
38     pre();
39     while(t--)
40     {
41         cin>>n>>m;
42         if(n-m==1) {
43         cout<<0<<endl;
44         continue;}
45          if(n==m) {
46         cout<<1<<endl;
47         continue;}
48         if(m==0) {
49         cout<<d[n]<<endl;
50         continue;}
51         LL tmp=fac[n]*inf[m]%mod*inf[n-m]%mod*d[n-m]%mod;
52         cout<<tmp<<endl;
53     }
54     return 0;
55 }

View Code