Contest Duration: - (local time) (100 minutes) Back to Home

## 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.

#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: