[AGC026D]Histogram Coloring

\[\color{red}{\text{校长者,真神人也,左马桶,右永神,会执利笔破邪炁,何人当之?}} \\ \begin{array}{|} \hline \color{pink}{\text{The principal is really a god}} \\ \color{pink}{\text{with a closestool on the left and Yongshen on the right}} \\ \color{pink}{\text{holding a sharp pen to pierce the truth}} \\ \color{pink}{\text{Who can resist him? }} \\ \hline \end{array} \\ \begin{array}{|} \hline \color{green}{\text{校長は本当に神であり、左側にトイレ、右側にヨンシェンがあり}} \\ \color{green}{\text{鋭いペンを持って真実を突き刺している。誰が彼に抵抗できるだろうか? }} \\ \hline \end{array} \\ \begin{array}{|} \hline \color{lightblue}{\text{Le principal est vraiment un dieu}} \\ \color{lightblue}{\text{avec des toilettes à gauche et Yongshen à droite}} \\ \color{lightblue}{\text{tenant un stylo pointu pour percer la vérité}} \\ \color{lightblue}{\text{Qui peut lui résister ? }} \\ \hline \end{array} \\ \begin{array}{|} \hline \color{purple}{\text{Der Direktor ist wirklich ein Gott}} \\ \color{purple}{\text{mit einer Toilette links und Yongshen rechts}} \\ \color{purple}{\text{der einen spitzen Stift hält}} \\ \color{purple}{\text{um die Wahrheit zu durchdringen.}} \\ \color{purple}{\text{Wer kann ihm widerstehen? }} \\ \hline \end{array} \\ \begin{array}{|} \hline \color{cyan}{\text{Principalis deus est, Yongshen a dextris cum latrina}} \\ \color{cyan}{\text{acuto stylo ad perforandum veritatem: quis resistet ei? }} \\ \hline \end{array} \\ \color{red}{\text{对曰:“无人,狗欲当之,还请赐教!”}} \\ \newcommand\bra[1]{\left({#1}\right)} \newcommand\Bra[1]{\left\{{#1}\right\}} \newcommand\dx[0]{\text{dx}} \newcommand\string[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}} \newcommand\down[2]{{#1}^{\underline{#2}}} \newcommand\ddiv[2]{\left\lfloor\frac{#1}{#2}\right\rfloor} \newcommand\udiv[2]{\left\lceil\frac{#1}{#2}\right\rceil} \newcommand\lcm[0]{\operatorname{lcm}} \newcommand\set[1]{\left\{{#1}\right\}} \]

壹、题目描述 ¶

传送门 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) \]

第一个不用解释,解释一下第二个转移。

  • 第一个部分考虑的是 \(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;
}

肆、关键 の 地方 ¶

真的是人类智慧题,这个性质太离谱了。不过,这再一次印证了笛卡尔树对于直方图有奇效。

上一篇:存储技术: DAS NAS SAN


下一篇:CF寒假补题集——B. Palindromes Coloring