AtCoder ABC172 E - NEQ（组合数 + 容斥原理）

题目链接：https://atcoder.jp/contests/abc172/tasks/abc172_e

题意：从$m$个数中选择分别选择$n$个数组合成两个序列$A,B$，满足$A_i!=B_i$且每个序列都没有相同的数，问这样的序列一共有多少对。

思路：首先，我们可以考虑从$m$个数里面选择$n$个数，一共可以组成多少个序列，答案就是$A_m^n$，这样就相当于确定了$A$序列的个数。这样我们就可以知道$B$序列的个数就是从$m$个数里选择$n$个数，其中第$i$个数不为$i$的序列个数。 那该怎么求呢？这时候就可以用容斥原理啦！ 第$i$个数不为$i$的并集和 = 总数 - 一个数不为$i$ + 两个数不为$i$ - 三个数不为$i$ + … 这样答案就出来啦，具体实现详见代码。

AC代码：

#define _CRT_SECURE_NO_WARNINGS 1 #include <set> #include <map> #include <stack> #include <queue> #include <cmath> #include <ctime> #include <vector> #include <cstdio> #include <string> #include <iomanip> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define LL long long #define pii pair<int,int> #define sd(x) scanf("%d",&x) #define slld(x) scanf("%lld",&x) #define pd(x) printf("%d\n",x) #define plld(x) printf("%lld\n",x) #define rep(i,a,b) for(int i = (a) ; i <= (b) ; i++) #define per(i,a,b) for(int i = (a) ; i >= (b) ; i--) #define mem(a) memset(a,0,sizeof(a)) #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 #define fast_io ios::sync_with_stdio(false) const LL mod = 1e9 + 7; const int maxn = 5e5 + 7; const int INF = 0x3f3f3f3f; const double pi = acos(-1.0); LL f[maxn],inv[maxn]; void init() { inv[0] = f[0] = inv[1] = f[1] = 1; for(LL i = 2 ; i <= maxn ; i++) { inv[i] = ((mod - mod / i) * inv[mod%i]) % mod; f[i] = i; } for(LL i = 2 ; i <= maxn ; i++) { inv[i] = (inv[i] * inv[i-1]) % mod; f[i] = (f[i] * f[i-1]) % mod; } } LL C(LL x,LL y) { return f[x] * inv[y] % mod * inv[x-y] % mod; } LL A(LL x,LL y) { return f[x] * inv[x-y] % mod; } int main() { #ifndef ONLINE_JUDGE // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); long _begin_time = clock(); #endif init(); int n,m; sd(n),sd(m); LL ans = A(m,n); for(LL i = 1 ; i <= n ; i++) { LL res = C(n,i) * A(m - i , n - i) % mod; if(i&1) ans = (ans - res + mod) % mod; else ans = (ans + res) % mod; } ans = ans * A(m,n) % mod; plld(ans); #ifndef ONLINE_JUDGE long _end_time = clock(); // cout << "time = " << _end_time - _begin_time << endl; #endif return 0; }