容斥原理

UVA - 11806

题意：

求在一个n*m的矩阵中选择k个，使得每个边界上至少有一个被选择。

做法：

容斥。

代码：

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
const int N = 5e3 + 7, mod = 1e6 + 7;
int fact[N],inv[N];
int n, m, k;
int c[N][N];

int qmi(int a,int b) {
    int res = 1ll % mod;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    } return res % mod;
}

int C(int n,int m) {
    return c[n][m];
}

void init() {
    for (int i = 0; i < N; ++ i ) c[i][0] = 1;
    for (int i = 0; i < N; ++ i ) c[i][i] = 1;
    for (int i = 1; i < N; ++ i ) {
        for (int j = 1; j < N; ++ j ) c[i][j] = c[i-1][j-1] + c[i-1][j], c[i][j] %= mod;
    } 
}

int T;

void solve(){
    printf("Case %lld: ", ++ T);
    cin >> n >> m >> k;
    int ans = 0;
    for (int i = 0; i < 16; ++ i ) {
        int r = n, c = m, cnt = 0;
        for (int j = 0; j <= 3; ++ j ) {
            if (i & (1 << j)) {
                ++ cnt;
                if (j == 0 || j == 1) -- r;
                else -- c; 
            }
        }
        int fg = cnt & 1 ? -1 : 1;
        ans = ((ans + fg * C(r * c, k)) % mod + mod) % mod; 
    }
    cout << ans << endl;
}

signed main() {
    init();
    int t; cin >> t; while (t-- )
    solve();
    return 0;
}

HDU - 4135

题意：

求出区间内与n互质的数的个数。

做法：

枚举n的质因子，求出与n不互质的数的集合，容斥得到答案。

代码：

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
int n, m, k;
int T;
vector<int> mid;
int f(int x) {
    int ans = 0;
    for (int i = 0; i < (1 << mid.size()); ++ i ) {
        int now = 1; int cnt = 0;
        for (int j = 0; j < mid.size(); ++ j ) {
            if ((1 << j) & i) now *= mid[j], ++ cnt;
        }
        int fg = cnt & 1 ? -1 : 1;
        ans = ((ans + fg * (x / now))) ;
    }
    return ans;
}
void solve(){
    mid.clear();
    int a,b; cin >> a >> b >> n;
    for (int i = 2; i <= n / i; ++ i) {
        if (n < i) break;
        if (n % i == 0) {
            mid.emplace_back(i);
            while (!(n % i))  n /= i;
        }
    }
    if (n > 1) mid.emplace_back(n);
    printf("Case #%lld: ", ++ T);
    cout << f(b) - f(a - 1) << endl;
}
signed main() {
    int t; cin >> t; while(t--)
    solve();
    return 0;
}

HDU - 1465

题意：

n封信对应n个信封

求恰好全部装错了信封的方案数

做法：

容斥

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int fact[N];
int C(int n,int m) {
    int s = 1ll;
    for (int i =n -m + 1; i <= n; ++ i ) s *= i;
    for (int i = 1; i <= m; ++ i) s /= i; return s;
}
void solve(){
    
    while (cin >> n ) {
        int ans = fact[n];
        for (int i = 1; i <= n; ++ i ) {
            int fg = i & 1 ? -1 : 1;
            ans += fg * C(n, i) * fact[n - i];
        }
        cout << ans << endl;
    }
}

signed main() {
    fact[1] = 1;fact[0 ] = 1;
    for (int i = 2; i <= 22; ++ i ) fact[i] = fact[i - 1] * i;
    solve();
    return 0;
}

http://acm.hdu.edu.cn/showproblem.php?pid=6397

题意:

在[0, n - 1]中可重复地任意选m个数，使得和为k的方案数。

做法：

考虑在k个1中插入m-1个隔板，可以得到每两个隔板之间至少有1个1的方案数，题目要求可以有0个1，那么把所有隔板先都填上1个1，此时有k + m个1，插m-1个隔板，即可得到不考虑所选数的上届的答案。题目要求所选的数在[0,n-1]之间，减去上界不合法的方案数即可得到答案。对于上界不合法方案数的求法，运用容斥原理，减去至少有1个n的，加上至少有2个n的，减去至少有3个n的…

代码：

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
#define int long long 
const int N = 2e5 + 7, mod = 998244353;
int fact[N],inv[N];
int n, m, k;

int qmi(int a,int b) {
    int res = 1 % mod; a %= mod;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    } return res % mod;
}

int C(int n,int m) {
    if (n < m) return 0;
    return fact[n] * inv[n - m] % mod * inv[m] % mod;
}

void init() {
    inv[0] = fact[0] = 1;
    for (int i = 1; i < N; ++ i ) fact[i] = fact[i - 1] * i % mod;
    inv[N - 1] = qmi(fact[N - 1], mod - 2);
    for (int i = N - 2; i >= 1; -- i ) inv[i] = inv[i + 1] * (i + 1) % mod;
}

void solve(){
    cin >> n >> m >> k;
    int cnt = (k + m - 1) / n;
    int ans = 0;
    for (int i = 0; i <= cnt; ++ i ) {
        int fg = i & 1 ? -1 : 1;
        ans = ((ans + fg * C(m, i) * C(k + m - 1 - i * n, m - 1) % mod) + mod) % mod;
    }
    cout << ans % mod << endl; 
}

signed main() {
    init();
    int t; cin >> t; while ( t-- )
    solve();
    return 0;
}

https://codeforces.com/gym/103428/problem/M

题意：

求在游戏场次为n，胜场数为m的条件下，最长连胜为k的方案数。

做法：

同上

代码：

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
#define int long long 
const int N = 2e5 + 7, mod = 998244353;
int fact[N],inv[N];
int n, m, k;

int qmi(int a,int b) {
    int res = 1ll % mod;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    } return res % mod;
}

int C(int n,int m) {
    if (n < m) return 0;
    return fact[n] * inv[n - m] % mod * inv[m] % mod;
}

void init() {
    fact[0] = inv[0] = 1;
    for (int i = 1; i < N; ++ i ) fact[i] = fact[i-1] * i % mod;
    inv[N - 1] = qmi(fact[N - 1], mod - 2);
    for (int i = N - 2; i >= 1; -- i) inv[i] = inv[i + 1] * (i + 1) % mod;
}

int f(int n,int m,int k) {
    int ans = 0; ++ k;
    int cnt = n - m + 1;
    for (int i = 0; i <= cnt; ++ i ) {
        int fg = i & 1 ? -1 : 1;
        ans = ((ans + fg * C(cnt, i) * C(m - i * k + cnt - 1, cnt - 1) % mod) % mod + mod) % mod;
    }
    return ans % mod;
}

void solve(){
    cin >> n >> m >> k;
    cout << ((f(n, m, k) - f(n, m,  k - 1) % mod) + mod ) % mod << endl;
}

signed main() {
    init();
    solve();
    return 0;
}

HDU - 5768

题意：

找出区间内是7的倍数，并且满足xx%p_i==a_i的个数。

做法：

容斥，CRT求方程组的解，快速乘防止爆long long

代码：

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
const int N = 2e5 + 7;
int a[N],b[N];
int ta[N], tb[N];
bool v[N];
int n, m, k, T, l, r;

int exgcd(int a,int b,int &x,int &y) {
    if (!b) {
        x = 1, y = 0; return a;
    }
    int d = exgcd(b, a % b, x, y);
    int z = x; x  = y; y = z - y * (a / b);
    return  d;
}

int qmul(int a,int b,int mod) {
    int res = 0;
    while (b) {
        if (b & 1) res = (res + a) % mod;
        a = (a + a) % mod; b >>= 1;
    }
    return res;
}

int CRT(int a[],int m[],int n) { // a是余数，m是模数，n是方程个数
    int M = 1, r = 0;
    for (int i = 0; i <= n; ++ i) M *= m[i];
    for (int i = 0, Mi, x ,y; i <= n; ++ i) {
        Mi = M / m[i];
        int d = exgcd(Mi, m[i], x ,y);
        x = (x % M + M) % M;
        r = (r + qmul(qmul(a[i], Mi, M), x, M)) % M;
        r %= M;
    }
    if (r < 0) r += M;
    return r;
}

void solve() {
    cin >> n >> l >> r;
    -- l;
    for (int i = 1; i <= n; ++ i) cin >> a[i] >> b[i];
    int ans = 0;
    for (int i = 0; i < (1 << n); ++ i) {
        int cnt = 0, mm = 7;
        for (int j = 0; j < n; ++ j) {
            if ((1 << j) & i) ta[++cnt] = b[j + 1], tb[cnt] = a[j + 1], mm *= a[j + 1];
        }
        int fg = cnt & 1 ? -1 : 1;
        int res = CRT(ta, tb, cnt);
        if (res > r) continue;
        int num = (r - res) / mm + 1; // 求个数
        if (l >= res) num = num - 1 -  (l - res) / mm;
        ans += fg * num;
    }
    printf("Case #%lld: %lld\n",  ++ T, ans);
}

signed main() {
    a[0] = 7;
    ta[0] = 0; tb[0] = 7;
    int t; cin >> t; while (t--) 
    solve();
    return 0;
}