【題解】Google Code Jam 2021 Round 2 pC Hidden Pancakes

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int t, n, a[100005], p = 1e9+7;
long long fac[100005], inv[100005];
vector <int> v[100005];

int power(int a, int b){
    long long mul = a, ret = 1;
    while (b){
        if (b & 1){
            ret *= mul;
            ret %= p;
        }
        mul *= mul;
        mul %= p;
        b >>= 1;
    }
    return ret;
}
int c(int n, int k){
    if (k > n) return 0;
    return ((fac[n] * inv[k]) % p * inv[n-k]) % p;
}
int f(int l, int r, int tar){
    if (l > r) return 1;
    auto it = upper_bound(v[tar].begin(), v[tar].end(), r);
    if (it == v[tar].begin()) return 0;
    it--;
    if (*it < l || r < *it) return 0;
    long long ret = 1;
    ret *= f(l, *it-1, tar);
    ret %= p;
    ret *= f(*it+1, r, tar+1);
    ret %= p;
    ret *= c(r-l, *it-l);
    ret %= p;
    //cout << l << " " << r << " " << tar << " " << ret << "\n";
    return ret;
}

int main(){
    cin >> t;
    fac[0] = 1;
    inv[0] = 1;
    fac[1] = 1;
    inv[1] = 1;
    for (int i = 2; i <= 100000; i++){
        fac[i] = (fac[i-1]*i) % p;
        inv[i] = power(fac[i], p-2);
    }
    for (int Case = 1; Case <= t; Case++){
        cin >> n;
        for (int i = 1; i <= n; i++){
            v[i].clear();
        }
        for (int i = 1; i <= n; i++){
            cin >> a[i];
            v[a[i]].push_back(i);
        }
        cout << "Case #" << Case << ": " << f(1, n, 1) << "\n";
    }
}