AtCoder AGC 026 D - Histogram Coloring (橙色, 1100 点)

なんか yukicoder で書いた問題に前半は似てた。でもこの問題の難しいところは後半の方だった。。。

問題へのリンク

問題概要

幅が マス、高さが のヒストグラムが与えられる。このヒストグラムの各マスを白黒に塗る方法のうち

• どの 2 × 2 の区間をとっても、白2個+黒2個となっている

ようなものを数え上げよ。1000000007 で割ったあまりで。

制約

• 
• 

考えたこと

まずは長方形の場合を考える。その場合は

• ある段が「白黒白黒...」「黒白黒白...」のときは、その上下の段は「白黒反転」か「同じもの」
• ある段がそれ以外のときは、その上下の段は「白黒反転」のみ

という感じになる。

そこで

• dp[ ヒストグラム H ] := H を白黒に塗る方法の数
• dp2[ ヒストグラム H] := そのうち最下段が「白黒白黒」か「黒白黒白」になっているものの数

という風にすれば、再帰的にきれいに解くことができる。

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

const int MOD = 1000000007;

typedef pair<long long, long long> pll;
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

int N;
vector<long long> H;

// first: all, second: oxoxoxoxox
pll rec(int left, int right) {
    long long resall = 0, resalt = 0;

    // height
    long long height = 1LL<<60;
    for (int i = left; i < right; ++i) if (H[i] < height) height = H[i];
    for (int i = left; i < right; ++i) H[i] -= height;
    vector<pll> subs;
    int nleft = left;
    int width = 0;
    for (int i = left; i < right; ++i) {
        if (H[i] == 0) {
            if (i > nleft) subs.push_back(rec(nleft, i));
            nleft = i+1;
            ++width;
        }
    }
    if (right > nleft) subs.push_back(rec(nleft, right));
    
    // second
    long long facalt = 1;
    for (auto p : subs) facalt *= p.second, facalt %= MOD;
    resalt += facalt * modpow(2LL, height, MOD) % MOD;
    resalt %= MOD;
    
    // first
    resall += resalt;
    long long fac = 1;
    for (auto p : subs) {
        fac *= (p.first + p.second); fac %= MOD;
    }
    resall += fac * modpow(2LL, width, MOD) % MOD;
    resall += MOD - facalt * 2 % MOD;
    resall %= MOD;
    
    // result
    return pll(resall, resalt);
}

int main() {
    cin >> N;
    H.resize(N); for (int i = 0; i < N; ++i) cin >> H[i];
    pll res = rec(0, N);
    cout << res.first << endl;
}