C - Ubiquity Editorial by evima


Let us consider all sequences \(\{A\}\) of lengths \(N\) that consists of $\(0 \leq A_i \leq 9\).

The number of \(\{A\}\) such that there does not exist an \(i\) such that \(A_i = 0\) is \(9^N\).

The number of \(\{A\}\) such that there does not exist an \(i\) such that \(A_i = 9\) is \(9^N\).

The number of \(\{A\}\) such that there does not exist an \(i\) such that \(A_i = 0\) nor \(A_i = 9\) is \(9^N\).

The number of \(\{A\}\) such that satisfies at least one of “there does not exist an \(i\) such that \(A_i = 0\)” or “there does not exist an \(i\) such that \(A_i = 9\)” is \(9^N + 9^N - 8^N\).

The number of \(\{A\}\) is \(10^N\).

The number of \(\{A\}\) such that satisfies both of “there exists \(i\) such that \(A_i = 0\)” and “there exists \(i\) such that \(A_i = 9\) is \(10^N-9^N-9^N+8^N\).

The answer is \(10^N-9^N-9^N+8^N\).

This solution is an application of inclusion-exclusion theorem. Inclusion-exclusion theorem is useful for more difficult problems.

解答例(C++)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;

ll powmod(ll x,ll y){
    ll res=1;
    for(ll i=0;i<y;i++){
        res=res*x%mod;
    }
    return res;
}
int main(){
    ll n;
    cin>>n;
    ll ans=powmod(10,n)-powmod(9,n)-powmod(9,n)+powmod(8,n);
    ans%=mod;
    ans=(ans+mod)%mod;
    cout<<ans<<"\n";
}

posted:
last update: