[ABC178C] Ubiquity 题解

cloud2764scallop_eve · 2024-01-02 23:03:49 · 题解

题意

有一个长为 n 的数列 a_1,a_2,...,a_n ，其中对于每个 a_i 都有 0 \le a_i \le 9 ，并保证数列中至少有一个 a_i 为 0 且至少有一个 a_i 为 9 。输入 n ，输出满足条件的序列的个数对 10^9+7 取模之后的余数。

思路

简单到爆炸的容斥原理。

考虑四个集合：

1. 所有序列；
2. 包含 0 的序列；
3. 包含 9 的序列；
4. 既包含 0 又包含 9 的序列。

它们的数量分别是：

那么根据容斥原理可得，ans = 10^n - 2 \times 9^n + 8^n。

由于数据较大，需要快速幂。

代码

注意 long long 和取模。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7;
int n;
ll tq, th1, tnh2;
ll qpow(ll a, ll b, ll mod) {
    ll ret = 1;
    while (b) {
        if (b & 1) ret = ret * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ret;
}
int main() {
    scanf("%d", &n);
    tq = qpow(10, n, mod), th1 = qpow(9, n, mod), tnh2 = qpow(8, n, mod);
    th1 *= 2;
    ll ans = ((tq - (th1 - tnh2) % mod) + mod) % mod;
    printf("%lld", ans);
    return 0;
}