Submission #3419544


Source Code Expand

#include <iostream>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;

template <typename T, typename U>
T mypow(T b, U n) {
    if (n == 0) return 1;
    if (n == 1) return b % MOD;
    if (n % 2 == 0) {
        return mypow(b * b % MOD, n / 2);
    } else {
        return mypow(b, n - 1) * b % MOD;
    }
}

ll dp[50][1 << 18];
// dp[i][S] = i個の数値でSが作れるパターン数

int main() {
    int N, X, Y, Z;
    cin >> N >> X >> Y >> Z;
    int W = X + Y + Z;

    fill(dp[0], dp[45], 0);
    dp[0][0] = 1;

    ll ans = 0;

    for (int i = 0; i <= N; ++i) {
        for (int S = 0; S < (1 << W); ++S) {
            if (((S >> (X - 1)) & 1) && ((S >> (X + Y - 1)) & 1) && ((S >> (X + Y + Z - 1)) & 1)) {
                ans += dp[i][S] * mypow(10LL, N - i);
                ans %= MOD;
                dp[i][S] = 0;
            }
        }

        for (int S = 0; S < (1 << W); ++S) {
            for (int k = 1; k <= 10; ++k) {
                int T = ((S << k) + (1 << (k - 1))) & ((1 << W) - 1);
                dp[i + 1][T] += dp[i][S];
                dp[i + 1][T] %= MOD;
            }
        }
    }

    cout << ans << endl;
    return 0;
}

Submission Info

Submission Time
Task E - Iroha and Haiku
User Tiramister
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1235 Byte
Status AC
Exec Time 333 ms
Memory 94464 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 4
AC × 35
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt
All subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_max1.txt, subtask1_max2.txt, subtask1_max3.txt, subtask1_min1.txt, subtask1_min2.txt, subtask1_min3.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 54 ms 94464 KB
subtask0_sample_02.txt AC 62 ms 94464 KB
subtask0_sample_03.txt AC 25 ms 94464 KB
subtask0_sample_04.txt AC 333 ms 94464 KB
subtask1_01.txt AC 25 ms 94464 KB
subtask1_02.txt AC 30 ms 94464 KB
subtask1_03.txt AC 26 ms 94464 KB
subtask1_04.txt AC 29 ms 94464 KB
subtask1_05.txt AC 25 ms 94464 KB
subtask1_06.txt AC 25 ms 94464 KB
subtask1_07.txt AC 26 ms 94464 KB
subtask1_08.txt AC 25 ms 94464 KB
subtask1_09.txt AC 25 ms 94464 KB
subtask1_10.txt AC 25 ms 94464 KB
subtask1_11.txt AC 25 ms 94464 KB
subtask1_12.txt AC 44 ms 94464 KB
subtask1_13.txt AC 30 ms 94464 KB
subtask1_14.txt AC 25 ms 94464 KB
subtask1_15.txt AC 37 ms 94464 KB
subtask1_16.txt AC 143 ms 94464 KB
subtask1_17.txt AC 46 ms 94464 KB
subtask1_18.txt AC 79 ms 94464 KB
subtask1_19.txt AC 50 ms 94464 KB
subtask1_20.txt AC 31 ms 94464 KB
subtask1_21.txt AC 75 ms 94464 KB
subtask1_22.txt AC 49 ms 94464 KB
subtask1_23.txt AC 47 ms 94464 KB
subtask1_24.txt AC 36 ms 94464 KB
subtask1_25.txt AC 50 ms 94464 KB
subtask1_max1.txt AC 333 ms 94464 KB
subtask1_max2.txt AC 318 ms 94464 KB
subtask1_max3.txt AC 173 ms 94464 KB
subtask1_min1.txt AC 25 ms 94464 KB
subtask1_min2.txt AC 25 ms 94464 KB
subtask1_min3.txt AC 54 ms 94464 KB