壹、题目描述 ¶
贰、题解 ¶
看似好像很难，不过确实很难，我们无从下手。这提醒着我们，对此题挖掘性质。
记得做过类似的题，不难发现，当我们确定某个矩阵的三个点后，剩下的点也可以确定了，但是缺一个角的情况好像有点复杂，我们只考虑两个方块：
如果相邻两个方块同色，那么包含它的一个 \(2\times 2\) 的正方形的剩下两个方块只有一种涂法，而且这两个方块的颜色一样，都是前两个方块的颜色的反；
如果相邻两个方块不同色，那么包含它的一个 \(2\times 2\) 的正方形的剩下两个方块有两种涂法，只需要两个方块颜色不同即可；
那么，我们进一步拓展 —— 当某一层是交错填色，那么下一层也只需要交错填色，下一层可以有两种填法，但是，若该层并非严格交错填色，那么下一层无论如何，对应位置都只能是该层取反。
接下来我们就可以考虑建出笛卡尔树之后进行树 \(\rm DP\) 了。设 \(dp(u,1)\) 表示 \(u\) 管辖的区域是交错填色，\(dp(u,0)\) 表示 \(u\) 子树中合法填色方案，而 \(u\) 管辖的矩阵为 \(H\times W\)，其中有 \(cnt_u\) 个和 \(u\) 是同一高度，那么
\[dp(u,1)=2^H\prod_{v\in son_u} dp(v,1) \\ dp(u,0)=2^{cnt_u}\prod_{v\in son_u}(dp(v,0)+dp(v,1))+(2^H-2)\prod_{v\in son_u} dp(v,1) \]第一个不用解释，解释一下第二个转移。
- 第一个部分考虑的是 \(u\) 管辖的矩阵的第一行随便填的情况，首先，由于和 \(u\) 同一高度的点不会包含在任何方阵中，所以他们可以任意填色，而剩下的部分就是儿子所管辖的部分，由于我们当前考虑的是当前随便填，显然，当前行与上一行完全取反是一种合法情况，至于为什么还要算上 \(dp(v,1)\) 呢？如果上一行是交错填数，那么当前行 “照抄” 上一行显然也是合法情况。至于除了第一行的剩下行？全部暴力按照上一行整体取反；
- 但是还剩下一部分？这部分就是全部都是交错填数的情况，这就要第二种来计算了。它的解释和 \(dp(u,1)\) 很像，不过为什么有 \(-2\) 呢？因为 \(dp(v,0)\) 亦包含 \(v\) 中交错填数的情况，我们在考虑非照抄部分的时候，是按照整体取反来做的，也就是说，在第一个部分中，第一行在某些特殊情况下也是交错颜色的，而 \(cnt_u\) 个任取的颜色也恰好是交错且整体是可以衔接的，后面行也是在上一行基础上取反，这导致后面也是颜色交错，这种情况一共有两种，减去即可；
按照这个转移即可。复杂度 \(\mathcal O(N\log H)\)，因为有快速幂。
叁、参考代码 ¶
# include <cstdio>
# include <algorithm>
# include <cstring>
# include <vector>
using namespace std;
# define NDEBUG
# include <cassert>
namespace Elaina {
# define rep(i, l, r) for(int i=(l), i##_end_=(r); i<=i##_end_; ++i)
# define drep(i, l, r) for(int i=(l), i##_end_=(r); i>=i##_end_; --i)
# define fi first
# define se second
# define mp(a, b) make_pair(a, b)
# define Endl putchar('\n')
# define mmset(a, b) memset(a, b, sizeof (a))
# define mmcpy(a, b) memcpy(a, b, sizeof (a))
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
template <class T> inline T fab(T x) { return x<0? -x: x; }
template <class T> inline void getmin(T& x, const T rhs) { x=min(x, rhs); }
template <class T> inline void getmax(T& x, const T rhs) { x=max(x, rhs); }
template <class T> inline T readin(T x) {
x=0; int f=0; char c;
while((c=getchar())<'0' || '9'<c) if(c=='-') f=1;
for(x=(c^48); '0'<=(c=getchar()) && c<='9'; x=(x<<1)+(x<<3)+(c^48));
return f? -x: x;
}
template <class T> inline void writc(T x, char s='\n') {
static int fwri_sta[55], fwri_ed=0;
if(x<0) putchar('-'), x=-x;
do fwri_sta[++fwri_ed]=x%10, x/=10; while(x);
while(putchar(fwri_sta[fwri_ed--]^48), fwri_ed);
putchar(s);
}
} using namespace Elaina;
const int maxn=100;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
inline int qkpow(int a, int n) {
int ret=1;
for(; n>0; n>>=1, a=1ll*a*a%mod)
if(n&1) ret=1ll*ret*a%mod;
return ret;
}
int h[maxn+5], n;
inline void input() {
n=readin(1);
rep(i, 1, n) h[i]=readin(1);
}
int rt, ncnt;
int dp[maxn+5][2];
void solve(int& u, int l, int r, int c) {
u=++ncnt;
dp[u][0]=dp[u][1]=1;
int mn=inf, cnt, lst, H;
vector <int> son;
rep(i, l, r) mn=min(mn, h[i]);
rep(i, l, r) if(h[i]==mn)
son.push_back(i);
lst=l-1, cnt=son.size(), H=mn-c;
son.push_back(r+1); /** push @p r+1 after update @p cnt */
for(int p: son) {
if(lst+1<=p-1) {
int v; solve(v, lst+1, p-1, mn);
dp[u][1]=1ll*dp[u][1]*dp[v][1]%mod;
dp[u][0]=1ll*dp[u][0]*(dp[v][0]+dp[v][1])%mod;
} lst=p;
}
dp[u][0]=(1ll*dp[u][0]*qkpow(2, cnt)%mod+1ll*dp[u][1]*(qkpow(2, H)+mod-2)%mod)%mod;
dp[u][1]=1ll*dp[u][1]*qkpow(2, H)%mod;
}
signed main() {
input();
solve(rt, 1, n, 0);
writc(dp[rt][0]);
return 0;
}
肆、关键 の 地方 ¶
真的是人类智慧题，这个性质太离谱了。不过，这再一次印证了笛卡尔树对于直方图有奇效。