Official
C - Ubiquity Editorial by ynymxiaolongbao
\(0 \leq A_i \leq 9\) なる長さ \(N\) の整数列 \(\{A\}\) 全体について考えます。
\(A_i=0\) なる \(i\) が存在しないような \(\{A\}\) は、\(9^N\) 通りあります。
\(A_i=9\) なる \(i\) が存在しないような \(\{A\}\) は、\(9^N\) 通りあります。
\(A_i=0\) なる \(i\) と \(A_i=9\) なる \(i\) がともに存在しないような \(\{A\}\) は、\(8^N\) 通りあります。
\(A_i=0\) なる \(i\) と \(A_i=9\) なる \(i\) の少なくとも一方が存在しないような \(\{A\}\) は、\(9^N+9^N-8^N\) 通りあります。
\(\{A\}\) は、\(10^N\) 通りあります。
\(A_i=0\) なる \(i\) と \(A_i=9\) なる \(i\) がともに存在するような \(\{A\}\) は、\(10^N-9^N-9^N+8^N\) 通りあります。
答えは \(10^N-9^N-9^N+8^N\) です。
この解法は包除原理の適用であるといえます。 包除原理はより難易度の高い問題を解く際にも活躍します。
#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: