ARC023 C - タコヤ木

問題文

http://arc023.contest.atcoder.jp/tasks/arc023_3

解法

典型 of 典型みたいな問題．

L -1 -1 ... -1 R
みたいな区間に分けて考えて，R - L を -1 にうまく分配するという問題になる．
これはいわゆる重複組合せというやつ．高校数学でも頻出．
というか，
http://abc021.contest.atcoder.jp/tasks/abc021_d
これと全く同じ問題になる．
今回は A の値がでかいので，factテーブルを 10^5 まで持つとかはできないけど，区間が 2000 と小さいので nCr を愚直に求めていける．
逆元は，mod が素数だから分母を Y として Y^(p - 2) で求められる．（フェルマーの小定理）

あとは得られた値をそれぞれかけてやればOK．

ソースコード

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

using ll = long long;
using pii = pair<int, int>;

constexpr ll M = 1e9 + 7;

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

int main() {
    int N;
    cin >> N;
    vector<pii> v;
    int l = -1, r = -1;
    int cnt = 0;
    for(int i = 0; i < N; ++i) {
        int a;
        cin >> a;
        if(a != -1) {
            l = r;
            r = a;
            if(l != -1) {
                v.emplace_back(r - l + 1, cnt);
                cnt = 0;
            }
        } else {
            cnt++;
        }
    }
    ll res = 1;
    for(auto& p : v) {
        ll P = 1;
        for(int i = p.first + p.second - 1; i >= p.first; --i) {
            P = (P * i) % M;
        }
        ll Q = 1;
        for(int i = 1; i <= p.second; ++i) {
            Q = (Q * i) % M;
        }
        Q = modpow(Q, M - 2);
        P = (P * Q) % M;
        res = (res * P) % M;
    }
    cout << res << endl;
}

感想

nCr 求めるときに n がでかいとびびっちゃうことがたまにある．
だいたい r が小さいので求められるやんけ！というところまでセット．