Submission #3100763


Source Code Expand

Copy
#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

constexpr ll MOD = 1e9 + 7;

ll POW(ll a, ll b) {
    ll result = 1;
    while (b) {
        if (b & 1) {
            result *= a;
            result %= MOD;
        }
        a *= a;
        a %= MOD;
        b /= 2;
    }
    return result;
}

ll combination(ll a, ll b) {
    ll n = 1, m = 1;
    for (ll i = 1; i <= b; i++) {
        n *= a - i + 1;
        n %= MOD;
        m *= i;
        m %= MOD;
    }
    return n * POW(m, MOD - 2) % MOD;
}

int main() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }

    struct Blank {
        ll left, right, num;
    };
    vector<Blank> blanks;

    for (ll i = 0; i < N; i++) {
        if (A[i] == -1) {
            Blank b;
            b.left = A[i - 1];
            for (ll j = i + 1; j < N; j++) {
                if (A[j] != -1) {
                    b.right = A[j];
                    b.num = j - i;
                    i = j;
                    break;
                }
            }
            blanks.push_back(b);
        }
    }

    ll ans = 1;
    for (auto b : blanks) {
        ans *= combination(b.right - b.left + b.num, b.num);
        ans %= MOD;
    }
    cout << ans << endl;
}

Submission Info

Submission Time
Task C - タコヤ木
User tokumini
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1340 Byte
Status
Exec Time 2 ms
Memory 256 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 50 / 50 sample_01.txt, sample_02.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
Subtask2 30 / 30 sample_01.txt, sample_02.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, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt
Subtask3 20 / 20 sample_01.txt, sample_02.txt, sample_03.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, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt, subtask3_08.txt, subtask3_09.txt, subtask3_10.txt, subtask3_11.txt, subtask3_12.txt
Case Name Status Exec Time Memory
sample_01.txt 1 ms 256 KB
sample_02.txt 1 ms 256 KB
sample_03.txt 1 ms 256 KB
subtask1_01.txt 1 ms 256 KB
subtask1_02.txt 1 ms 256 KB
subtask1_03.txt 1 ms 256 KB
subtask1_04.txt 1 ms 256 KB
subtask1_05.txt 1 ms 256 KB
subtask1_06.txt 1 ms 256 KB
subtask1_07.txt 1 ms 256 KB
subtask1_08.txt 1 ms 256 KB
subtask1_09.txt 1 ms 256 KB
subtask1_10.txt 1 ms 256 KB
subtask1_11.txt 1 ms 256 KB
subtask1_12.txt 1 ms 256 KB
subtask2_01.txt 1 ms 256 KB
subtask2_02.txt 1 ms 256 KB
subtask2_03.txt 1 ms 256 KB
subtask2_04.txt 1 ms 256 KB
subtask2_05.txt 1 ms 256 KB
subtask2_06.txt 1 ms 256 KB
subtask2_07.txt 1 ms 256 KB
subtask2_08.txt 2 ms 256 KB
subtask2_09.txt 2 ms 256 KB
subtask2_10.txt 2 ms 256 KB
subtask2_11.txt 2 ms 256 KB
subtask2_12.txt 2 ms 256 KB
subtask3_01.txt 1 ms 256 KB
subtask3_02.txt 1 ms 256 KB
subtask3_03.txt 1 ms 256 KB
subtask3_04.txt 2 ms 256 KB
subtask3_05.txt 1 ms 256 KB
subtask3_06.txt 2 ms 256 KB
subtask3_07.txt 2 ms 256 KB
subtask3_08.txt 2 ms 256 KB
subtask3_09.txt 2 ms 256 KB
subtask3_10.txt 2 ms 256 KB
subtask3_11.txt 2 ms 256 KB
subtask3_12.txt 2 ms 256 KB