题解归档 - cf498E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf498E
• 本地来源：problems/cf498E/idea.md
• 题目链接：https://codeforces.com/contest/498/problem/E
• 原始标题：cf498E — Stairs and Lines

思路

cf498E — Stairs and Lines

题意

7 级阶梯，第 i 级宽 w_i、高 i，矩形从左到右拼接。给内部格子的边染色（外边界视为已染），要求没有任何格子四边全染。旋转视为不同方案，求方案数 mod 1e9+7。

思路

从左到右扫「竖线层」。对高度 h，用长度 h 的 bitmask 表示当前最右竖线上哪些内部竖边已染。相邻两层之间枚举 (h-1) 条横边的取法，若某行出现「左竖+右竖+上下横边」四边全染则非法。

预处理转移矩阵 M[h][s2][s1]：状态 s1 到 s2 的合法横边方案数。同一高度连续 w_h 列等价于乘 M[h]^w_h（矩阵快速幂）。

高度从 h 升到 h2（中间 w=0）时，新增行的外侧竖边已固定为染，状态从 s 扩展到 s ^ ((1<<h2)-(1<<h))。

初态：首个非零 w_fir 对应高度 fir，右边界全染，即状态 (1<<fir)-1 方案数为 1。答案为最终向量在状态 (1<<last)-1 的分量。

复杂度

状态至多 128，预处理 7 种高度；每次矩阵乘 O(128^3)，快速幂 O(log w_i)。总复杂度 O(128^3 · Σ log w_i)。

实现注意

• check 与矩阵乘法循环变量勿与 main 共用全局 i,j，否则外层循环被破坏。
• 样例：0 2 0 0 0 0 0 → 7；5 1 0 3 0 0 1 → 411199181。

参考

Codeforces Round #284 Editorial (498E)。

代码

来源：problems/cf498E/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:30:10
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll md=1e9+7;
ll n,i,j,k,zc,pd,cur,dq,cnt,ans;
ll a[10];
struct tnode{
    ll n,m;
    ll p[130][130];
};
tnode t[10],now;
tnode mul(const tnode &u,const tnode &v){
    tnode res;
    ll x,y,z;
    res.n=u.n;
    res.m=v.m;
    for(x=0;x<u.n;x++){
        for(y=0;y<v.m;y++){
            res.p[x][y]=0;
            for(z=0;z<u.m;z++){
                res.p[x][y]=(res.p[x][y]+u.p[x][z]*v.p[z][y])%md;
            }
        }
    }
    return res;
}
tnode matpow(tnode u,ll x){
    tnode res;
    ll y;
    res.n=u.n;
    res.m=u.m;
    for(y=0;y<u.n;y++){
        for(cur=0;cur<u.m;cur++) res.p[y][cur]=0;
        res.p[y][y]=1;
    }
    while(x){
        if(x&1) res=mul(u,res);
        x>>=1;
        u=mul(u,u);
    }
    return res;
}
ll chk(ll s1,ll s2,ll s,ll x){
    ll u,v;
    u=2*s+1;
    u|=(1<<x);
    for(v=0;v<x;v++){
        if((s1&(1<<v)) and (s2&(1<<v)) and (u&(1<<v)) and (u&(1<<(v+1)))) return 0;
    }
    return 1;
}
void cal(){
    ll h,u,v,w;
    for(h=1;h<=7;h++){
        t[h].n=(1<<h);
        t[h].m=(1<<h);
        for(u=0;u<(1<<h);u++){
            for(v=0;v<(1<<h);v++){
                t[h].p[v][u]=0;
                for(w=0;w<(1<<(h-1));w++){
                    if(chk(u,v,w,h)) t[h].p[v][u]++;
                }
            }
        }
    }
}
int main(){
    cal();
    for(i=1;i<=7;i++) cin>>a[i];
    cur=1;
    while(!a[cur]) cur++;
    now.n=(1<<cur);
    now.m=1;
    for(i=0;i<now.n;i++) now.p[i][0]=0;
    now.p[(1<<cur)-1][0]=1;
    for(i=cur;i<=7;){
        now=mul(matpow(t[i],a[i]),now);
        zc=i+1;
        while(zc<=7 and !a[zc]) zc++;
        if(zc==8){
            cout<<now.p[(1<<i)-1][0]<<"\n";
        }
        else{
            pd=(1<<zc)-(1<<i);
            now.n=(1<<zc);
            for(j=0;j<(1<<i);j++){
                now.p[j^pd][0]=now.p[j][0];
                now.p[j][0]=0;
            }
        }
        i=zc;
    }
    return 0;
}