blog

精進メモ：AtCoder Beginner Contest 178 C - Ubiquity

Nov 05, 2020, 16:46 #Procon

問題：AtCoder Beginner Contest 178 C - Ubiquity

Difficulty: 587

包除原理 |A∨B| = |A| + |B| - |A∧B| と mod 1000000007 の問題。

AC

// C
#include <stdio.h>

#define MOD 1000000007

int main(void) {
    int n;
    scanf("%d", &n);

    long long a, b, c;
    a = b = c = 1;
    for (int i = 0; i < n; i++) {
        a = a * 10 % MOD;
        b = b *  9 % MOD;
        c = c *  8 % MOD;
    }
    long long ans = (a - 2*b + c) % MOD;
    if (ans < 0) ans += MOD;

    printf("%lld\n", ans);
    return 0;
}

引き算の mod はマイナスの値になることがあるので、その場合は 1000000007 を足す。

引き算して 1000000007 を足してから mod を取っても同じ。