[AtCoder] ABC 178 C – Ubiquity

2020年9月13日2020年12月13日

問題

方針

組み合わせ

全ての数列の組み合わせは \( 10^N \) 個あります。\( 0 \) または \( 9 \) が存在しない数列の組合せは \( 9^N \) 個あります。\( 0 \) と \( 9 \) が存在しない数列の組み合わせは \( 8^N \) 個あります。

ここで、全ての組み合わせの集合を \( U \)、\( 0 \) が存在しない集合を \( A \)、\( 9 \) が存在しない集合を \( B \) とすると、求める集合は、

\[ U – A – B + A \cap B\]

となります。したがって、求めるものは

\[ 10^N – 2 \times 9^N + 8^N\]

となります。

動的計画法

ここで、配列 \( d \) を次のように定義します。

1. \( d(i, 0)\) : \( i \) 個の整数列で \( 0 \) と \( 9 \) を含まないものの個数
2. \( d(i, 0)\) : \( i \) 個の整数列で \( 0 \) を含まないものの個数
3. \( d(i, 0)\) : \( i \) 個の整数列で \( 9 \) を含まないものの個数
4. \( d(i, 0)\) : \( i \) 個の整数列で \( 0 \) と \( 9 \) を含むものの個数

初期値は \( d(0, 0) = 1 \) とし、更新式は、

\begin{eqnarray}
d(i + 1, 0)&=& 8d(i, 0)\\
d(i + 1, 1)&=& d(i, 0) + 9d(i, 1)\\
d(i + 1, 2)&=& d(i, 0) + 9d(i, 2)\\
d(i + 1, 3)&=& d(i, 1) + d(i, 2) + 10d(i, 3)
\end{eqnarray}

となります。したがって、\( d(N, 3) \) が答えです。

コード

組み合わせ

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

ll mod = pow(10, 9) + 7;

ll modpow(ll a, ll n) {
    if (mod <= 0) return 0;
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

int main() {
    ll N;
    cin >> N;
    ll ans = modpow(10, N) - 2 * modpow(9, N) + modpow(8, N);
    ans = (ans + mod * 100) % mod;
    cout << ans << "\n";
    return 0;
}

動的計画法

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

ll dp[1000001][4]{};

int main() {
    int N;
    cin >> N;
    ll mod = pow(10, 9) + 7;
    dp[0][0] = 1;
    for (int i = 0; i < N; i++) {
        dp[i + 1][0] = dp[i][0] * 8;
        dp[i + 1][1] = dp[i][0] + dp[i][1] * 9; 
        dp[i + 1][2] = dp[i][0] + dp[i][2] * 9;
        dp[i + 1][3] = dp[i][3] * 10 + dp[i][1] + dp[i][2];
        for (int j = 0; j < 4; j++) {
            dp[i + 1][j] %= mod;
        }
    }
    cout << dp[N][3] << "\n";
    return 0;
}

感想

これ解けなくてちょびっと涙が出た。