题意
有一个长为 \(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\) 取模之后的余数。
思路
简单到爆炸的容斥原理。
考虑四个集合：
- 所有序列；
- 包含 \(0\) 的序列；
- 包含 \(9\) 的序列；
- 既包含 \(0\) 又包含 \(9\) 的序列。
它们的数量分别是：
\[10^n,9^n,9^n,8^n
\]
那么根据容斥原理可得，\(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;
}