AtCoder Regular Contest 023 C - タコヤ木

問題

　広義単調増加列のうち一部分が不明となっている列が与えられる。あり得る組み合わせの数を求めよ。

解法

　不明な部分が連続している一つの塊に注目する。たとえば定数についてという部分列を考えるとすると、からに至るまでの4回の遷移の総和がとなっているということになる。これは個の増加操作が3個の仕切りによって区切られるような場合の数を数えることで計算できる。つまり一般に-1が個続く場合にはを求めればよい。100,000,007についての余りを求めることに注意して累乗計算を高速化すればこの方針で間に合う。

反省

　1時間18分(4WA)でAC。33分で80点の部分点解法を出したが、それ以降分からずうつらうつらしていたら1時間以上経っていたので解説スライドを見た。方針は考えていたままだった。の求め方として、いつも通りの累乗とその逆元を事前計算する実装でやったための数が大きいときだめだなーと思っていたのだった。つまり

//fact[i]とinv_fact[i]は事前計算してある
ll combination(ll a, ll b) {
    return fact[a] * inv_fact[a - b] % MOD * inv_fact[b] % MOD;
}

　としていたのだが、別にすべて事前計算する必要はないためその場で必要なものを計算していけばよいのだった。

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);
}

　その場計算の方が汎用性が高いのだろうか。どうせが大きかったら事前計算でもダメなわけで、事前計算で可能だがこちらではダメという例があるのかどうか。しかしこういう実装もアドホックで考えていくことが大切そうだ。

コード

#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;
}