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\) です。

この解法は包除原理の適用であるといえます。 包除原理はより難易度の高い問題を解く際にも活躍します。

解答例(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: