Derangements

time limit per test 1 second memory limit per test 256 megabytes
You are given two s: n and m.

Let D be the number of permutations of the set {1,2,…,n+m} such that the first m values are not fixed points of the permutation. Formally, we are interested in permutations p such that for each j between 1 and m, inclusive, we have p(j) != j.

Compute and return D modulo 1,000,000,007.

传送门:TC717C

题解

题目简洁明了 就是求长度为n+m的全排列中 有从1-m都是p(j)!=j的排列总数
超级好的一道容斥题
公式:
错排
理解了容斥自然理解了这公式
顺便把以前的装错信封用容斥重新写了下
一个小问题 就是以后再也不用pow了 垃圾pow偏大一点会有误差

AC code:(不包含输入类)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
//非本题代码
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
FastScanner sc = new FastScanner();
PrintWriter pw = new PrintWriter(System.out);
ZuHeShu z=new ZuHeShu();
z.init();
while (sc.hasNext()) {
int n=sc.nextInt();
long sum=0;
for(int i=0;i<=n;i++){
long t=1;
for(int j=1;j<=n-i;j++){
t*=j;
}
sum+=(int)Math.pow(-1, i)*C(i,n)*t;
//pw.println(sum);
}
pw.println(sum);
pw.flush();
}
}
static long C(long a,long b){
//b!/(a!*(b-a)!)
long t=Math.min(a,b-a);
double result=1.0;
while(t>0){
result*=(b*1.0/t);
b--;
t--;
}
return (long)(result+0.5);
}
}
class ZuHeShu{
long C[][]=new long[1000][1000];
long MOD=100000007;
void init(){
C[1][0] = C[1][1] = 1;
for (int i = 2; i < 1000; i++){
C[i][0] = 1;
for (int j = 1; j < 1000; j++)
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]);
}
}
}