C - Ubiquity 解説 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";
}
投稿日時:
最終更新: