ARC023 C - タコヤ木
解法
典型 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 が小さいので求められるやんけ!というところまでセット.