传送门 to AtCoder.
看似好像很难,不过确实很难,我们无从下手。这提醒着我们,对此题挖掘性质。
记得做过类似的题,不难发现,当我们确定某个矩阵的三个点后,剩下的点也可以确定了,但是缺一个角的情况好像有点复杂,我们只考虑两个方块:
如果相邻两个方块同色,那么包含它的一个 \(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) \]第一个不用解释,解释一下第二个转移。
按照这个转移即可。复杂度 \(\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; }
真的是人类智慧题,这个性质太离谱了。不过,这再一次印证了笛卡尔树对于直方图有奇效。