AGC 026 D

一个很神仙的 dp，这题完全可以出到 $n \le 10^5$ 啊不知道为啥只有 100。。

考虑，第一行是黑白相间的，那么后面都必须黑白相间，有反色和复读两种情况。而如果第一行不是黑白相间的，那么下一行的构造就只能反色，所以一个第一行不是黑白相间的情况对应唯一一种方案。

然后我们可以按照套路类似笛卡尔树上的 dp，设 $dp[u][0/1]$ 表示当前在笛卡尔树的 $u$ 节点，这个节点所包含的区间是黑白相间 / 任意排列，然后考虑怎么转移，设当前在节点 $u$ ，它下一层一共有 $v_1,v_2,\dots v_k$ 个节点，一共有 $w$ 个这一层的最小值，这一层到上一层的距离为 $x$ 那么有：

$dp [u][0]=2^{x} \prod_{i=1 . . k} dp [v_i][0]\\dp [u][1]=2^{w} \prod_{i=1 . . k}\left(dp[v_i][0]+dp[v_i][1]\right)+\left(2^{x}-2\right) \prod_{i=1 . . k} dp [v_i][0]$

因为考虑，如果这一层是黑白交错，那么下一层也必须黑白交错，而黑白交错每一层可以反色或者复读，所以系数是 $2^x$ 。

如果这层任意填，我们考虑如果这 $x$ 层全程在复读，那么这一层到下一层有两种情况：

这一层和在 $v$ 区间的下一层一摸一样，也就是说这里下一层的方案数量是 $dp[v][1]$ ，这种情况系数是 $2^w$ ，因为空的格子可以任意安排。
这一层和咋 $v$ 区间的下一层相反了，也就是说这里下一层的方案数量是 $dp[v][0]$ ，这种情况系数也是 $2^w$ ，因为空的格子可以任意安排。

这两种情况加起来才是 $v$ 对 $u$ 的贡献，应根据乘法原理乘起来。

考虑如果这里的 $x$ 层并非一直复读，而是黑白交错的跑，也就是前面的第一个方程那样（因为我们算的是总方案数量），那么本来应该就是第一个方程的值，但是其中有两种情况，也就是黑白黑白黑白… 和白黑白黑… 也是可以全程复读的，这两种情况应该减去，于是就是最后的答案辣！

cpp

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "vector"
using namespace std;
#define MAXN 116
#define P 1000000007
int n;
int A[MAXN];
int Pow( int x , int a ) {
    int cur = x % P , ans = 1;
    while( a ) {
        if( a & 1 ) ans = 1ll * ans * cur % P;
        cur = 1ll * cur * cur % P , a >>= 1;
    }
    return ans;
}
pair<int,int> solve( int l , int r , int c ) {
//    cout << l << ' ' << r << endl;
    if( l > r ) return make_pair( 1 , 0 );
    int h = 0x3f3f3f3f;
    for( int i = l ; i <= r ; ++ i ) h = min( h , A[i] );
    vector<int> pos;
    pos.push_back( l - 1 );
    for( int i = l ; i <= r ; ++ i ) if( A[i] == h ) pos.push_back( i );
    pos.push_back( r + 1 );
    int nm = pos.size() - 2;
    int re = 1 , tot = 1;
    for( int i = 0 ; i < pos.size() - 1 ; ++ i ) {
        pair<int,int> ret = solve( pos[i] + 1, pos[i + 1] - 1, h );
        re = 1ll * re * ret.first % P , tot = 1ll * tot * ( ret.first + ret.second ) % P;
//        cout << l << ' ' << r << ' ' << pos[i] + 1 << ' ' << pos[i + 1] << ' ' << re << ' ' << tot << endl;
    }
    return make_pair( 1ll * re * Pow( 2 , h - c ) % P , ( 1ll * re * ( Pow( 2 , h - c ) - 2 ) % P + 1ll * Pow( 2 , nm ) * tot % P ) % P );
}
int main() {
    cin >> n;
    for( int i = 1 ; i <= n ; ++ i ) scanf("%d",&A[i]);
    cout << solve( 1 , n , 0 ).second << endl;
}