Problem Statement
You are given two ints: 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.
Definition
Class:
DerangementsDiv2
Method:
count
Parameters:
int, int
Returns:
int
Method signature:
int count(int n, int m)
(be sure your method is public)
Limits
Time limit (s):
2.000
Memory limit (MB):
512
Stack limit (MB):
512
Constraints
n will be between 0 and 50, inclusive.
m will be between 1 and 50, inclusive.
Examples
0)
0
2
Returns: 1
Here we are looking for permutations of {1, 2} such that p(1) != 1 and p(2) != 2. There is only one such permutation: the permutation (2, 1). In other words, the permutation p such that p(1) = 2 and p(2) = 1.
1)
2
1
Returns: 4
Here we are counting permutations of {1, 2, 3} such that p(1) != 1. There are four such permutations: (2, 1, 3), (2, 3, 1), (3, 1, 2), and (3, 2, 1). Here, (a, b, c) denotes a permutation p for which p(1) = a, p(2) = b, and p(3) = c.
2)
1
2
Returns: 3
This time we want permutations of {1, 2, 3} such that p(1) != 1 and p(2) != 2. The three such permutations are (2, 1, 3), (2, 3, 1), and (3, 1, 2).
3)
3
5
Returns: 21234
4)
20
27
Returns: 88437461
Watch out for integer overflow.
【题目链接】:
【题意】
给你两个整数n和m;
然后让你求1..n+m的一些满足以下要求的排列p的个数:
要求i从1..m满足p[i]!=i;
【题解】
容斥原理搞;
设ci表示1..m中有i个位置满足pi==i的方案数;
ci=C(m,i)*(n+m-i)!
则答案就为(n+m)!-c1∪c2∪c3…..∪cm
减号右边那个东西,用容斥原理搞
为了不重复计数;
先加上每一个位置都不同的方案,然后减去有两个位置不同的方案,然后加上有3个位置不同的方案,然后减去有4个位置不同的方案…
【Number Of WA】
0
【反思】
取模过程中会出现负数的话,要注意加上MOD数;
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)
#define Open() freopen("F:\\rush.txt","r",stdin)
#define Close() ios::sync_with_stdio(0)
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };
const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };
const double pi = acos(-1.0);
const int N = 50+5;
const LL MOD = (int) 1e9 + 7;
//head
LL c[N][N],fac[N+N];
class DerangementsDiv2
{
public:
int count(int n, int m)
{
rep1(i, 1, 50)
c[i][i] = c[i][0] = 1;
rep1(i, 1, 50)
rep1(j, 1, i - 1)
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
fac[0] = 1;
rep1(i, 1, 100)
fac[i] = (fac[i - 1] * i) % MOD;
LL ans = fac[n + m],temp = 0,p = 1;
rep1(i, 1, m) {
temp += (p*c[m][i]%MOD + MOD) % MOD*fac[n + m - i] % MOD;
p = -p;
}
ans = ((ans - temp)%MOD + MOD) % MOD;
return (int) ans;
}
};