[AGC026D] Histogram Coloring 题解
给定 \(n\) 列的网格，每列高为 \(h_i\)，将每个格子染色成红色或蓝色，使得每个 \(2\times 2\) 的区域都恰好有两个蓝格子和两个红格子，求方案数（对 \(10^9+7\) 取模）。
\(1\leq n\leq 100,1\leq h_i\leq 10^9\)
性质
为了方便讲述，先假设 \(h_i=h_{i+1}\)，第 \(i\) 列第 \(j\) 行的染色状态记为 \(a_{i,j}\)。下面这些东西画一下一下就明白了。
如果存在 \(a_{i,j}=a_{i,j+1}\)，就是说前一列中出现两个连续颜色相同格子，那么后一列中每格颜色必须和前一列相反。反之如果前一列颜色是交错的，那么后一列颜色既可以和前一列相同，也可以和前一列相反（答案 \(\times 2\)）
显然 \(h_i\) 不一定等于 \(h_{i+1}\)，如果 \(a_{i,j}=a_{i,j+1},\forall k<j,a_{i,k}\neq a_{i,k+1}\) 而 \(h_{i+1}\leq j\)，那么前一列中连续同色格就影响不到后一列；如果 \(h_{i+1}\geq j+1\)，那么后一列 \(j+1\) 及往上的行就可以随便染色，前一列无法限制。
\(h_i\leq 10^3\)
首先让我们忽略 \(h_i\) 是个 \(10^9\) 的数，考虑它和 \(n\) 同量级怎么做。
我们定义 \(dp_{i,j}\) 为考虑到第 \(i\) 列，且第 \(i\) 列前 \(j\) 个格子颜色都是交错而 \(a_{i,j}\neq a_{i,j+1}\) 的方案数。
如果 \(h_{i}>h_{i-1}\)，那么 \(a_{i,h_i}\sim a_{i,h_{i+1}}\) 是可以自由填色不受前一列限制的，有转移
\[dp_{i,j}=dp_{i-1,j}\times 2^{a_i-a_{i-1}}\quad j\leq a_{i-1} \]而对于 \(j>a_{i-1}\) 的情况，该列可以自由填数的位置就是 \(j+1\sim a_i\) 了，又需要兼顾前一列的答案，有转移
\[dp_{i,j}=dp_{i-1,a_{i-1}}\times 2^{a_i-j} \quad a_{i-1}<j<a_i \]对于 \(j=a_{i}\)，需要特殊考虑，根据前面性质，颜色交错要么和前列相同要么相反
\[dp_{i,a_i}=dp_{i-1,a_{i-1}}\times 2 \]如果 \(h_i\leq h_{i-1}\)，可以得到以下转移，方法原理比上面一种情况还简单一些
\[dp_{i,j}=dp_{i-1,j} \quad j< a_i\\ dp_{i,a_i}=\sum_{j=a_i}^{a_{i+1}}2\times dp_{i-1,j} \]统计答案就是 \(\sum a_{n,j}\)，总的复杂度是 \(O(nh)\) 的。
拓展到 \(10^9\)
将 \(h_i\) 离散化，数据存在 \(lis\) 数组里面，然后我们定义 \(f_{i,j}=\sum\limits_{k=lis_{j-1}+1}^{lis_j}dp_{i,k}\)。
对于第二个式子 \(dp_{i,j}=dp_{i-1,a_{i-1}}\times 2^{a_i-j} \quad a_{i-1}<j<a_i\)，可以得到
\[f_{i,j}=dp_{i-1,a_{i-1}}\times (2^{a_i-lis_j}+2^{a_i-lis_j+1}+\cdots 2^{a_i-lis_{j-1}-1}) \]等比数列求和即可。对于其他的式子，转移比较显然。
重点是我们会发现我们的 \(dp_{i,a_i}\) 是特殊判断的，也就是说我们用 \(f_{i,k}\) （其中 \(lis_k=a_i\)）是不能根据上面式子转移的，我们需要重新定义一下 \(f_{i,k}=dp_{i,a_i}\) 而不是一段数的和。实现方法很简单，离散化的时候将 \(a_i-1\) 加入 \(lis\) 数组即可。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll P=1000000007;
const int N=103;
int n;ll h[N],lis[N*N],a[N],dp[N][N*2];int tot;
inline ll fpr(ll b,ll t,ll x=1ll){
for(;t;t>>=1,b=b*b%P)
if(t&1)x=x*b%P;
return x;
}
inline ll sumr(ll l,ll r){//2^l+...+2^r
return fpr(2ll,l)*(fpr(2ll,r-l+1)-1+P)%P;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%lld",&h[i]);
lis[++tot]=h[i];
if(h[i]>1)lis[++tot]=h[i]-1;
}
lis[++tot]=1;
sort(lis+1,lis+1+tot);
tot=unique(lis+1,lis+1+tot)-lis-1;
for(int i=1;i<=n;++i)
a[i]=lower_bound(lis+1,lis+1+tot,h[i])-lis;
a[0]=1;dp[0][a[0]]=1;
for(int i=1;i<=n;++i){
if(a[i]>a[i-1]){
for(int j=1;j<a[i];++j){
if(j<=a[i-1])dp[i][j]=dp[i-1][j]*fpr(2ll,lis[a[i]]-lis[a[i-1]])%P;
else dp[i][j]=dp[i-1][a[i-1]]*sumr(lis[a[i]]-lis[j],lis[a[i]]-lis[j-1]-1)%P;
}
dp[i][a[i]]=2*dp[i-1][a[i-1]]%P;
}else{
for(int j=1;j<=a[i-1];++j){
if(j<a[i])dp[i][j]=dp[i-1][j];
else dp[i][a[i]]=(dp[i][a[i]]+2*dp[i-1][j])%P;
}
}
}
ll ans=0;
for(int j=1;j<=a[n];++j)
ans=(ans+dp[n][j])%P;
printf("%lld\n",ans);
return 0;
}
后记
高数课上推的，当时还没考虑 \(h_i\) 值域的问题，但是发现可以比较简单得拓展，虽然最后还是码了快 \(1\) 个小时。
标签：Coloring,AGC026D,题解,ll,times,leq,int,lis,dp From： https://www.cnblogs.com/BigSmall-En/p/18415789