题意：
给定n列的方块，第i列高度$h_i$。现在要把它染成红蓝两色，要求满足：对于任意一个$2\times 2$的区域，恰有2个蓝色，2个红色。问方案数。
$n\leq 100,h_i\leq10^9.$
题解：
观察到一个性质：对于同行相邻两个格子，如果颜色相同，那么下一行的颜色必定取反；否则下一行可以取反也可以不取。那么，对于任一行，如果存在相邻两个格子颜色相同，下一行的染色方法唯一；否则存在两种染色方案。（以下所述的“存在/不存在”都是指“存在/不存在相邻两个格子颜色相同”）
考虑保存两个量：first：存在相邻格子颜色相同情况的方案数；second：不存在的方案数（固定第一个格子的颜色，也就是最终答案需要乘2）。
如果是一个矩形很容易计算答案。否则定义solve(l,r,lim)表示区间[l,r]比lim高的部分染色方案数，每次对于这段区间把下面整块矩形的部分砍掉，上面部分递归处理。用s0,s1维护上方有方格的列，当前行存在/不存在的方案数，那么可以方便地和上方没有方格的部分合并答案。注意计数过程中一些细节问题。
时间复杂度$\mathcal{O}(n^2)$。
code：
#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define ll long long
#define inf 1000000001
#define y1 y1___
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
char gc(){
static char buf[],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
ll read(){
char ch=gc();ll x=;int op=;
for (;!isdigit(ch);ch=gc()) if (ch=='-') op=-;
for (;isdigit(ch);ch=gc()) x=(x<<)+(x<<)+ch-'';
return x*op;
}
#define N 105
#define mod 1000000007
int ksm(int x,int p){
int ret=;
for (;p;p>>=,x=(ll)x*x%mod) if (p&) ret=(ll)ret*x%mod;
return ret;
}
int n,h[N];
pii solve(int l,int r,int lim){//区间[l,r]比lim高的部分的方案数
int mi=inf,cnt=;pii ret;//first：存在相邻格子颜色相同情况的方案数；second：不存在的方案数（固定第一个格子的颜色）
rep (i,l,r) if (h[i]<mi) mi=h[i],cnt=;else if (h[i]==mi) cnt++;
if (cnt==r-l+){//矩形
ret.fi=(ksm(,r-l+)+mod-)%mod;
ret.se=ksm(,mi-lim-);
return ret;
}
int rest=r-l+,s0=,s1=,last=;//rest：上方没有方格的列数；s0,s1：维护上方有方格的列，当前行存在/不存在的方案数
rep (i,l,r+)
if (!last&&h[i]>mi) last=i;
else if (last&&(h[i]<=mi||i>r)){
rest-=i-last;
pii tmp=solve(last,i-,mi);//子问题，递归求解
s0=(ll)s0*(tmp.fi+4ll*tmp.se%mod)%mod;//*4是因为上一行可以取反，当前行亦然，2*2
s1=(ll)s1*(2ll*tmp.se%mod)%mod;
last=;
}
s0=(s0+mod-s1)%mod;
ret.fi=(ll)s0*ksm(,rest)%mod;//如果上方方格已经存在，剩下的列随意
ret.fi=(ret.fi+(ll)s1*(ksm(,rest)+mod-)%mod)%mod;//否则需要去掉两种不合法的情况
ret.se=(ll)s1*ksm(,mi-lim-)%mod;//固定第一个格子（第一行）颜色
return ret;
}
int main(){
n=read();rep (i,,n) h[i]=read();
if (n==){//注意特判
printf("%d\n",ksm(,h[]));
exit();
}
int ex=;
rep (i,,n) if (h[i]>h[i-]&&h[i]>h[i+]){
ex=(ll)ex*ksm(,h[i]-max(h[i-],h[i+]))%mod;
h[i]=max(h[i-],h[i+]);
}
pii ans=solve(,n,);
printf("%d",(ll)ex*(ans.fi+2ll*ans.se%mod)%mod);
return ;
}
易错：
n=1的时候需要特判，因为否则的话调用ksm的时候p会变负，导致TLE。