宽容的原则(很简单,关键在于实践)--标题
一班容斥原理的题目不能直接套那个公式,需要我们真正明白把多算的那块去掉,多去掉的那块补上的过程的含义
The Lottery
UVA - 10325
这道题和上面第二例子一样,只不过不能被N个数整除,只要枚举被1~N个数整除,把所有情况都找出来,套公式即可,这里值得注意的是lcm和gcd都具有结合律,也就是说lcm(a,b,c) = lcm(lcm(a,b),c)
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxm = 20;
ll num[maxm], n;
ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a % b);
}
ll lcm(ll a, ll b) {
return a / gcd(a, b) * b;
}
int m;
ll ans;
void dfs(int c, int cur, int i, ll now) {
if(cur == c) {
ans += ((c & 1) ? -1 : 1) * (n/now);
return;
}
while(i < m) {
dfs(c, cur+1, i+1, lcm(now, num[i]));
i++;
}
}
int main()
{
// freopen("/Users/maoxiangsun/MyRepertory/acm/i.txt", "r", stdin);
while(~scanf("%lld%d", &n, &m)) {
for(int i = 0; i < m; i++) {
scanf("%lld", num+i);
}
ans = n;
for(int i = 1; i <= m; i++) {
dfs(i, 0, 0, 1);
}
printf("%lld\n", ans);
}
return 0;
}
Cheerleaders
UVA - 11806
这道题的意思是一个n*m的方格表,每个方格最多放一个东西,我们要放k个东西,问在上下左右那几条边都有东西的前提下有多少种方式。
也是套那个公式,最后可以推出这样的结果:
a
n
s
=
C
(
n
m
,
k
)
−
2
(
C
(
(
n
−
1
)
m
,
k
)
+
C
(
(
m
−
1
)
n
,
k
)
)
+
(
C
(
(
n
−
2
)
m
,
k
)
+
C
(
(
m
−
2
)
n
,
k
)
+
4
C
(
(
m
−
1
)
(
n
−
1
)
,
k
)
−
2
C
(
m
−
2
)
(
n
−
1
)
,
k
)
−
2
C
(
C
(
m
−
1
)
(
n
−
2
)
,
k
)
+
C
(
(
m
−
2
)
(
n
−
2
)
,
k
)
;
ans = C(nm, k) -2(C((n-1)m, k)+C((m-1)n,k))\\ +(C((n-2)m,k)+C((m-2)n,k)+4C((m-1)(n-1), k)\\ -2C(m-2)(n-1),k)-2C(C(m-1)(n-2),k) +C((m-2)(n-2), k);
ans=C(nm,k)−2(C((n−1)m,k)+C((m−1)n,k))+(C((n−2)m,k)+C((m−2)n,k)+4C((m−1)(n−1),k)−2C(m−2)(n−1),k)−2C(C(m−1)(n−2),k)+C((m−2)(n−2),k);
还有就是组合数取模问题,利用杨辉三角那个样子打表处理这种n*m不是很大,比较合适,再不行就用Lucas定理……
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 420;
const ll mod = 1000007;
ll CC[maxn][maxn] = {0};
void init() {
CC[0][0] = 1;
for(ll i = 1; i < maxn; i++) {
CC[i][0] = 1;
for(ll j = 1; j <= i; j++) {
CC[i][j] = (CC[i-1][j-1] + CC[i-1][j])%mod;
}
}
}
ll C(ll n, ll m) {
return CC[n][m];
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
ll n,m,k;
ll T;
init();
cin >> T;int cas=0;
while(T--) {
cin >> n >> m >> k;
ll ans = (C(n*m,k)-(2*C((n-1)*m, k) + 2*(C(n*(m-1), k)) -C((m-2)*n, k) -C((n-2)*m, k) - 4*C((m-1)*(n-1) , k) + 2*C((m-2)*(n-1), k) + 2*
C((m-1)*(n-2),k)-C((m-2)*(n-2), k) ) );
while(ans < 0) {
ans += mod;
}
cout << "Case "<<++cas<<": ";
cout << ans % mod << endl;
}
return 0;
}
2018山东省赛F题
https://ac.nowcoder.com/acm/contest/123/F
这道题的意思是给出四个区间左右端点li,ri,从中取出x1,x2,x3,x4,问这四个值相邻元素不等的取法有多少种,可以用容斥想,S-不符合条件的总数。
情况1,只考虑两两相邻相等,可以分出四组来
情况2,在三个相邻相等和x1=x2&&x3=x4与x2=x3&&x1=x4公6组,不难发现在情况1中包含了情况2的可能所以要把多去的情况1加上去,加多少呢?加一倍,为啥?比如情况1在计算x1=x2的数量时已经计算了x3=x4的数量,而x3=x4的数量时又计算了x1=x2所以计算了两遍x1=x2&&x3=x4
情况3,x1=x2=x3=x4
这是最容易错的地方,我已开始做也是因为这wa了,为啥,情况1多算4次,情况2把6次减去了,情况3需要1次所以需要加上3倍的情况3才行!
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans;
ll l[5],r[5];
const ll mod = 1e9 + 7;
int main()
{
int T;
scanf("%d", &T);
while(T--) {
ans = 1;
for(int i = 0; i < 4; i++) {
// cin >> l[i] >> r[i];
scanf("%lld%lld", &l[i], &r[i]);
ans = ans * (r[i] - l[i] + 1) % mod;
}
ll left, right;
for(int i = 0; i < 4; i++) {
left = max(l[i], l[(i+1)%4]);
right = min(r[i], r[(i+1)%4]);
if(right >= left) ans=((ans-(right-left+1)*(r[(i+2)%4]-l[(i+2)%4]+1)%mod*(r[(i+3)%4]-l[(i+3)%4]+1)%mod)%mod+mod)%mod;
}
for(int i = 0; i < 4; i++) {
left = max(l[i], max(l[(i+1)%4], l[(i+2)%4]));
right = min(r[i], min(r[(i+1)%4], r[(i+2)%4]));
if(right >= left) ans = (ans + (right - left + 1) * (r[(i+3)%4] - l[(i+3)%4] + 1)%mod)%mod;
}
ll l1,l2,r1,r2;
for(int i = 0; i < 2; i++) {
l1 = max(l[i], l[i+1]);
r1 = min(r[i], r[i+1]);
l2 = max(l[(i+2)%4], l[(i+3)%4]);
r2 = min(r[(i+2)%4], r[(i+3)%4]);
if(l1 <= r1 && l2 <= r2) {
ans = (ans + (r1-l1+1)*(r2-l2+1)%mod)%mod;
}
}
left = l[0];
right = r[0];
for(int i = 1; i < 4; i++) {
left = max(l[i], left);
right = min(r[i], right);
}
if(right >= left) {
ans = (ans - (3*(right - left + 1))%mod + mod ) % mod;
}
printf("%lld\n", ans);
}
return 0;
}
上一篇: 容斥原理详解
下一篇: 宽容原则 原则和模板代码