容斥原理

acm

容斥原理

容斥原理的重点在于去消掉重复计算的,而不在于公式,就算你能熟练背出dfs()的公式也是没有用的, 只有合理的思考,保留覆盖问题的合理的集合才能做此处理.

L - Co-prime HDU - 4135

这是一道容斥原理入门题,非常的简单,只要计算A-B 内存在的所有的与所给的N互质的个数,对n质因数分解,得到的质因数.非这些质因数的倍数就是我们要求的数,算出所有质因数组成的集合U, 就可以得到答案了.

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<cstdio>
#include<iostream>
#include<bitset>
#include<cstring>
#define ll long long
const int maxn = 5e5;
using namespace std;

bitset<maxn> judge;
int prime[maxn];


int tot = 0;
ll l,r,n;
ll co[maxn];
void init(){
    judge.reset();
    tot = 0;
    for(int i = 2; i < maxn ; i++){
        if(!judge[i]){
            prime[tot++] = i;
        }
        for(int j = 0; j < tot ;j++){
            if(i*prime[j] >= maxn)break;
            judge[i*prime[j]] = 1;
            if(i%prime[j] == 0){
                break;
            }
        }
    }
}
int cnt = 0;
void slove(ll n){
    cnt = 0;
    for(int i = 0; i < tot && prime[i] <= n;i ++){
        if(n%prime[i] == 0){
            co[cnt++] = prime[i];
            while(n%prime[i] == 0){
                n /= prime[i];
            }
        }
    }
    if(n>1){
        co[cnt++] = n;
    }
}


ll cal(ll a){
    ll ans = a;
    ll temp = 1;
    int cc = 0;
    for(int i = 1; i < (1<<cnt); i++){
        temp = 1;
        cc = 0;
        for(int j = 0; j <cnt; j++){
            if(i & (1<<j)){
                temp *= co[j];
                cc ++ ;
            }
        }
        if(cc&1)ans -= a/temp;
        else ans += a/temp;
    }
    return ans;
}

int main(){
    int t=0,T;scanf("%d",&T);
    init();
    while(t++<T){
        scanf("%lld%lld%lld",&l,&r,&n);
        slove(n);
        printf("Case #%d: %lld\n",t,cal(r)-cal(l-1));
    }
}

M - Calculation 2 HDU - 3501 **

本题与上题最大的区别在于,这里求得是这些数的和,

不过问题不大,在所给的区间内, 1, n, 2n, 3n, …. 我们原来求得是个数,然而现在要求的是和, 可以看出,我们剔除1后, 将n提出,那里面就是(1+2+…+个数),求和公式一贴,注意取模,那这波就很稳了.

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<cstdio>
#include<iostream>
#include<bitset>
#include<cstring>
#define ll long long
const int maxn = 5e5;
using namespace std;
const int mod = 1000000007;
bitset<maxn> judge;
int prime[maxn];

int tot = 0;
ll l,r,n;
ll co[maxn];
void init(){
    judge.reset();
    tot = 0;
    for(int i = 2; i < maxn ; i++){
        if(!judge[i]){
            prime[tot++] = i;
        }
        for(int j = 0; j < tot ;j++){
            if(i*prime[j] >= maxn)break;
            judge[i*prime[j]] = 1;
            if(i%prime[j] == 0){
                break;
            }
        }
    }
}

ll sum(ll n){
    if(n%2==0){
        return ((n/2)%mod*((n+1)%mod))%mod;
    }else{
        return ((n+1)/2%mod*(n%mod))%mod;
    }
}

int cnt = 0;
void slove(ll n){
    cnt = 0;
    for(int i = 0; i < tot && prime[i] <= n;i ++){
        if(n%prime[i] == 0){
            co[cnt++] = prime[i];
            while(n%prime[i] == 0){
                n /= prime[i];
            }
        }
    }
    if(n>1){
        co[cnt++] = n;
    }
}

ll cal(ll a){
    ll ans = 0;
    ll temp = 1;
    int cc = 0;
    for(int i = 1; i < (1<<cnt); i++){
        temp = 1;
        cc = 0;
        for(int j = 0; j <cnt; j++){
            if(i & (1<<j)){
                temp *= co[j];
                cc ++ ;
            }
        }
        if(cc&1)ans += ((sum(a/temp)%mod)*(temp%mod))%mod;
        else ans -= ((sum(a/temp)%mod)*(temp%mod))%mod;
        ans = (ans%mod + mod)%mod;
    }
    return ans;
}

int main(){
    init();
    //FILE *fp;
    //fp = fopen("in.txt", "w+");
    //for(int r = 1; r < mod; r++){
    while(scanf("%lld",&r) && r){
        n = r;
        slove(n);
        printf("%lld\n",cal(r-1)%mod);
    }
}

偶然发现欧拉函数处理这道题也非常的快, 关键在与我们要知道 $$gcd(a,n)=1 时, gcd(a, n-a)=1 $$, 根据这个对称,我们就可以知道 与n 互质的phi[n]个数的平均值为n/2; 根据这个公式很快也就知道不互质的个数了.

A - Eddy’s爱好 HDU - 2204 **

这里我们要求的是有多少个$$m^k$$, k> 1 的这样个数的个数,显然,我们开根号就知道有多少$$m^2$$这样的数了,但是我们很容易就发现了$$2^6 = 4^3 = 8 ^2 = 64$$, 也就是我们需要用到容斥原理的地方.

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
49
50
51
52
#include<cstdio>
#include<iostream>
#include<bitset>
#include<cmath>
#define ll long long
const int maxn  = 18;
const double eps = 1e-8;
using namespace std;
int prime[maxn] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61};

ll power(ll a, ll k){
    ll ans = 1;
    while(k){
        if(k&1) ans = ans*a;
        a = a*a;
        k >>= 1;
    }
    return ans ;
}

ll cal(ll a){
    ll ans = 0;
    ll tmp = 1;
    int c = 0;
    for(int i = 1; i < (1<<maxn); i++){
        tmp = 1;
        c  = 0;
        for(int j = 0; j < maxn ; j++){
            if(i & (1 << j)){
                c ++ ;
                tmp *= prime[j];
            }
            if(tmp>61)break;
        }
        if(tmp > 65)continue;
        ll it = eps+pow(a, (double)1.0/tmp)-1;
        if(it +eps < 1)continue;
        //cout << tmp << " :  " <<  pow(a, (double)1.0/tmp) << endl;
        if(c & 1)ans += it;
        else ans -= it;
        //cout << ans << endl;
    }
    return ans+1;
}
ll n;

int main(){
    while(~scanf("%lld",&n)){
        printf("%lld\n",cal(n));
    }
    return 0;
}

B - Integer’s Power HDU - 3208

这道题目也是上一道题目的变形,我们这次要求的是指数最大数的和, 但是问题就存在与,我们在算两个集合的并的时候并不能按照题目所求的那个直接去减, 然而更直接的, 我们可以处理每个幂次存在多少个这样的数(合理的),对于第次的,是要删去他倍数的幂中重复的个数,就可以了.

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#define ll long long
const double eps = 1e-8;
const ll inf = (ll)(1e18) + 500;
const int maxn = 18;
using namespace std;

ll power(ll a, ll b){
    ll res = 1;
    while(b){
        if(b&1){
            double judge = 1.0 * inf/res;
            if(a > judge)return -1;
            res *= a;
        }
        b >>=1;
        if(a > inf/a && b > 0)return -1;
        a *= a;
    }
    return res;
}

ll fid(ll a, ll b){// 精确求a^(1.0/b)向下取整数
    ll r = (ll) (pow(double(a), 1.0/b) + eps);
    ll p = power(r, b);
    if(p == a) return r;
    if(p==-1 || p > a)return r-1;

    ll t = power(r+1, b);
    if(t != -1 && t <= a)return r+1;
    else return r;
}

ll cnt[110];

ll cal(ll n){
    if(n==1)return 1;
    memset(cnt, 0, sizeof cnt);
    int total;
    ll ans = 0;
    cnt[1] = n;
    for(int i = 2; i < 63; i++){
        cnt[i] = fid(n, (ll)i) - 1;
        if(cnt[i] == 0){
            total = i;
            break;
        }
    }
    //去除重复的
    for(int i = total - 1; i >= 1; i--){
        for(int j = 1; j < i; j++){
            if(i%j == 0)cnt[j] -= cnt[i];
        }
    }
    for(int i = 1; i < total; i++) {
        ans += i * cnt[i];
    }
    return ans;
}

int main(){
    ll a,b;while(~scanf("%lld%lld",&a,&b) && a){
        printf("%lld\n",cal(b)-cal(a-1));
    }
    return -1;
}

E - GCDHDU - 1695

这道题用容斥做其实不是很好.但是我看到别人的题解有些许震惊,预处理了1e5以内每个数的素因数,然后暴力枚举跑的

非常的意外,但是技能get, 这样考虑其实是蛮对的 1e5的数 素因数 平均也就5个 是可以暴力过的.

当然也可以用正解莫比乌斯反演.

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
49
50
51
52
53
54
55
56
57
58
#include<cstdio>
#include<bitset>
#include<iostream>
#include<vector>
#define ll long long
const int maxn = 1e5+5;
using namespace std;

bitset<maxn> judge;
int prime[maxn];
int tot = 0;
vector<int> x[maxn];
//预处理所有数的素因子
void init() {
    judge.reset();
    for (int i=0; i<maxn; i++) x[i].clear();
    for (int j=2; j<maxn; j+=2) x[j].push_back(2);
    for (int i=3; i<maxn; i+=2)
        if (!judge[i]) {
            for (int j=i; j<maxn; j+=i) {
                judge[j] = true;
                x[j].push_back(i);
            }
        }
}
int main(){
    init();int t=0,T;scanf("%d",&T);
    int a,b,c,d,k;
    while(t++<T){
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        if(k==0){
            printf("Case %d: 0\n",t);
            continue;
        }
        b/=k,d/=k;
        if(b>d){a = b; b = d; d = a;}
        ll ans = 0;
        for(int i = 1; i <= d; i++){
            k = min(i,b);
            ans += k;
            int cc,tmp;
            for(int j = 1; j < (1<<x[i].size()); j++){
                tmp = 1;
                cc = 0;
                for(int m = 0; m < x[i].size(); m++){
                    if(j & (1<<m)){
                        cc++;
                        tmp *= x[i][m];
                    }
                }
                if(cc&1) ans -= k/tmp;
                else ans += k/tmp;
            }
        }
        printf("Case %d: %lld\n",t,ans);
    }
    return 0;
}

莫比乌斯反演:

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long

using namespace std;

const int maxn = 1e5+10;

bool judge[maxn];
int prime[maxn],mu[maxn],phi[maxn];
int tot=0;
void init(){
    memset(judge, 0 , sizeof judge);
    mu[1] = 1;
    for(int i = 2; i <= maxn; i++){
        if(!judge[i]){
            prime[tot++]=i;
            mu[i] = -1;
            phi[i] = i-1;
        }
        for(int j = 0; j < tot; j++){
            if(i*prime[j]>=maxn)break;
            judge[i*prime[j]] = 1;
            if(i%prime[j] == 0){
                mu[i*prime[j]] = 0;
                phi[i*prime[j]] = phi[i]*prime[j];
                break;
            }else{
                mu[i*prime[j]] = -mu[i];
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
            }
        }
    }
}

ll slove(int n, int m){
    ll res = 0;
    int low = min(n,m);
    //计算n,m范围内存在的对数
    for(int i = 1; i <= low; i++){
        res += (ll)mu[i]*(n/i)*(m/i);
    }
    //
    ll temp= 0;
    for(int i = 1; i <= low; i++){
        temp += (ll)mu[i]*(low/i)*(low/i);
    }
    res -= temp/2;
    return res;
}


int main(){
    int a,b,c,d,k;init();
    int t=0,T;scanf("%d",&T);
    while(t++<T){
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        ll ans = 0;
        if(k){
            b/=k,d/=k;
            //cout << b << d << endl;
            ans = slove(b,d);
        }
        printf("Case %d: %lld\n",t,ans);
    }
    return 0;
}

I - 跳蚤 POJ - 1091 **

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include<cstdio>
#include<iostream>
#include<bitset>
#include<cstring>
#define ll long long
const int maxn = 1e3;
using namespace std;
int tot = 0;
int n,m;

struct BigInt{
    const static int mod = 10;
    int a[maxn], len;
    BigInt(){
        memset(a, 0, sizeof a);
        len = 1;
    }
    BigInt(ll v){
        memset(a, 0, sizeof a);
        len = 0;
        do{
            a[len++] = v%mod;
            v/=mod;
        }while(v);
    }
    BigInt operator +(const BigInt &b)const{
        BigInt res;
        res.len = max(len, b.len);
        for(int i = 0; i <= res.len; i++){
            res.a[i] = 0;
        }
        for(int i = 0; i < res.len; i++){
            res.a[i] += ((i < len)?a[i]:0) + ((i < b.len)?b.a[i]:0);
            res.a[i+1] += res.a[i]/mod;
            res.a[i] %= mod;
        }
        if(res.a[res.len] > 0) res.len++;
        return res;
    }
    //保证a>=b
    BigInt operator -(const BigInt &b)const{
        BigInt res;
        res.len = len;
        for(int i = 0; i <= res.len; i++){
            res.a[i] = 0;
        }
        for(int i = 0; i < res.len; i++){
            res.a[i] += (a[i]-b.a[i]);
            if(res.a[i]<0){
                res.a[i]+=10;
                res.a[i+1]--;
            }
        }
        while(res.a[res.len-1]==0 && res.len > 1)res.len--;
        return res;
    }

    BigInt operator *(const BigInt &b)const{
        BigInt res;
        for(int i = 0; i < len; i++){
            int up = 0;
            for(int j = 0; j < b.len; j++){
                int temp = a[i]*b.a[j] + res.a[i+j] + up;
                res.a[i+j] = temp%mod;
                up = temp/mod;
            }
            if(up != 0)
                res.a[i + b.len] = up;
        }
        res.len = len + b.len;
        while(res.a[res.len - 1] == 0 && res.len > 1)res.len--;
        return res;
    }

    void output(){
        for(int i = len-1; i >= 0; i--)
            printf("%d",a[i]);
    }

    void init(){
        memset(a, 0, sizeof a);
        len = 1;
    }
};

BigInt power(BigInt a, int b){
    BigInt ans = BigInt(1);
    while(b){
        if(b&1) ans = ans*a;
        a = a*a;
        b >>= 1;
    }
    return ans;
}

int p[maxn];

int main(){
    while(~scanf("%d%d",&n,&m)){
        int tot = 0;
        int mm = m;
        for(int i = 2; i <= m/i; i++){
            if(m%i==0){
                p[tot++] = i;
            }
            while(m%i==0){
                m/=i;
            }
        }
        if(m>1){
            p[tot++] = m;
        }
        BigInt ans = power(mm, n);
        ll tmp = 1;
        int c = 0;
        for(int i = 1; i < 1<<tot; i++){
            c = 0; tmp = mm;
            for(int j = 0; j < tot; j++)
            if(i & (1 << j)){
                c++;
                tmp/=p[j];
            }
            BigInt it = BigInt(tmp);
            if(c&1) ans = ans - power(it, n);
            else ans = ans + power(it, n);
            //ans.output();
            //puts("");
        }
        ans.output();
        puts("");
    }
    return 0;
}

最后一体

题目是ｎ个学生，三人一组，给定的tuple无法组成一组，问一共有多少种组法，　首先给定的tuple如果不冲突则视为可以进行容斥的对象．

对于不冲突的集合容斥,vis[][]标记一下,dfs写可能会好一些.

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
#pragma comment(linker,"/STACK:1024000000,1024000000")
#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long

using namespace std;
const int SIZE = 11000;
const int maxn = 1005;
struct BigInteger {
    int len, s[SIZE + 5];

    BigInteger () {
        memset(s, 0, sizeof(s));
        len = 1;
    }
    BigInteger operator = (const char *num) { //字符串赋值
        memset(s, 0, sizeof(s));
        len = strlen(num);
        for(int i = 0; i < len; i++) s[i] = num[len - i - 1] - '0';
        return *this;
    }
    BigInteger operator = (const int num) { //int 赋值
        memset(s, 0, sizeof(s));
        char ss[SIZE + 5];
        sprintf(ss, "%d", num);
        *this = ss;
        return *this;
    }
    BigInteger (int num) {
        *this = num;
    }
    BigInteger (char* num) {
        *this = num;
    }
    string str() const { //转化成string
        string res = "";
        for(int i = 0; i < len; i++) res = (char)(s[i] + '0') + res;
        if(res == "") res = "0";
        return res;
    }
    BigInteger clean() {
        while(len > 1 && !s[len - 1]) len--;
        return *this;
    }

    BigInteger operator + (const BigInteger& b) const {
        BigInteger c;
        c.len = 0;
        for(int i = 0, g = 0; g || i < max(len, b.len); i++) {
            int x = g;
            if(i < len) x += s[i];
            if(i < b.len) x += b.s[i];
            c.s[c.len++] = x % 10;
            g = x / 10;
        }
        return c.clean();
    }

    BigInteger operator - (const BigInteger& b) {
        BigInteger c;
        c.len = 0;
        for(int i = 0, g = 0; i < len; i++) {
            int x = s[i] - g;
            if(i < b.len) x -= b.s[i];
            if(x >= 0) g = 0;
            else {
                g = 1;
                x += 10;
            }
            c.s[c.len++] = x;
        }
        return c.clean();
    }

    BigInteger operator * (const int num) const {
        int c = 0, t;
        BigInteger pro;
        for(int i = 0; i < len; ++i) {
            t = s[i] * num + c;
            pro.s[i] = t % 10;
            c = t / 10;
        }
        pro.len = len;
        while(c != 0) {
            pro.s[pro.len++] = c % 10;
            c /= 10;
        }
        return pro.clean();
    }

    BigInteger operator * (const BigInteger& b) const {
        BigInteger c;
        for(int i = 0; i < len; i++) {
            for(int j = 0; j < b.len; j++) {
                c.s[i + j] += s[i] * b.s[j];
                c.s[i + j + 1] += c.s[i + j] / 10;
                c.s[i + j] %= 10;
            }
        }
        c.len = len + b.len + 1;
        return c.clean();
    }

    BigInteger operator / (const BigInteger &b) const {
        BigInteger c, f;
        for(int i = len - 1; i >= 0; --i) {
            f = f * 10;
            f.s[0] = s[i];
            while(f >= b) {
                f = f - b;
                ++c.s[i];
            }
        }
        c.len = len;
        return c.clean();
    }
    //高精度取模
    BigInteger operator % (const BigInteger &b) const{
        BigInteger r;
        for(int i = len - 1; i >= 0; --i) {
            r = r * 10;
            r.s[0] = s[i];
            while(r >= b) r = r - b;
        }
        r.len = len;
        return r.clean();
    }

    bool operator < (const BigInteger& b) const {
        if(len != b.len) return len < b.len;
        for(int i = len - 1; i >= 0; i--)
            if(s[i] != b.s[i]) return s[i] < b.s[i];
        return false;
    }
    bool operator > (const BigInteger& b) const {
        return b < *this;
    }
    bool operator <= (const BigInteger& b) const {
        return !(b < *this);
    }
    bool operator == (const BigInteger& b) const {
        return !(b < *this) && !(*this < b);
    }
    bool operator != (const BigInteger &b) const {
        return !(*this == b);
    }
    bool operator >= (const BigInteger &b) const {
        return *this > b || *this == b;
    }
    friend istream & operator >> (istream &in, BigInteger& x) {
        string s;
        in >> s;
        x = s.c_str();
        return in;
    }
    friend ostream & operator << (ostream &out, const BigInteger& x) {
        out << x.str();
        return out;
    }
}f[maxn];

void init(){
    f[0] = f[1] = 1;
    for(int i = 2; i < maxn; i++){
        f[i] = f[i-1]*((3*i-1)*(3*i-2)/2);
    }

}

int data[30][5], num[25], vis[4010];
void dfs(int cur, int total, int edge){
    num[total]++;
    for(int i = cur; i < edge; i++){
        int flag = 0;
        if(!vis[data[i][0]] && !vis[data[i][1]] && !vis[data[i][2]]){
            flag = 1;
        }
        if(!flag) continue;
        for(int j = 0; j < 3; j++){
            vis[data[i][j]] = 1;
        }
        dfs(i+1, total+1, edge);
        for(int j = 0; j < 3; j++){
            vis[data[i][j]] = 0;
        }
    }
}
int main(){
    init();
    int n,k;
    while(~scanf("%d%d",&n,&k)){
        for(int i = 0; i < k; i++){
            scanf("%d%d%d",&data[i][0],&data[i][1],&data[i][2]);
        }
        BigInteger ans = 0;
        memset(vis, 0, sizeof vis);
        memset(num, 0, sizeof num);
        dfs(0,0,k);
        for(int i = 0; i <= min(k, n); i+=2){
            ans = ans + f[n-i]*num[i];
        }
        for(int i = 1; i <= min(k, n); i+=2){
            ans = ans - f[n-i]*num[i];
        }
        cout << ans << endl;
    }
    return 0;
}

本文标题:容斥原理

文章作者:呼哧

发布时间:2017-08-17, 11:40:42

最后更新:2018-08-04, 02:47:34

原始链接:http://hu-chi.github.io/2017/08/17/acm/容斥原理/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 容斥原理
    1. 1.1. L - Co-prime HDU - 4135
    2. 1.2. M - Calculation 2 HDU - 3501 **
    3. 1.3. A - Eddy’s爱好 HDU - 2204 **
    4. 1.4. B - Integer’s Power HDU - 3208
    5. 1.5. E - GCDHDU - 1695
    6. 1.6. I - 跳蚤 POJ - 1091 **
    7. 1.7. 最后一体
|