【AtCoder Grand Contest 017 F】Zigzag | Mrsrz's blog

状压 DP。

题目大意：

有 $n$ 层，第 $i$ 层有 $i$ 个点，第 $i$（$1\leq i\lt n$）层第 $j$ 个点和第 $i+1$ 层第 $j$ 个和第 $j+1$ 个点之间有边（分别为向左和向右）。

现在要从第 $1$ 层的 $1$ 号点出发，走 $m$ 条路径到第 $n$ 层，且必须保证第 $i$ 条的每部分都不在第 $i+1$ 条右边（可以重合）。

有一些形如 $(A,B,0/1)$ 的限制条件，表示第 $A$ 条路径在第 $A$ 层必须往左/右走。

求方案数。

题解：

设 $f_{i,j,S}$ 表示当前考虑到第 $i$ 条路径的第 $j$ 个位置，当前最左可以达到状态 $S$，当前的方案数。

枚举下一位，分类讨论：

• 下一位选 $0$，必须保证 $S$ 的这一位为 $0$。直接转移，状态仍为 $S$。
• 下一位选 $1$，且 $S$ 的这一位为 $1$。直接转移，状态仍为 $S$。
• 下一位选 $1$，且 $S$ 的这一位为 $0$。那么新的状态 $T$ 为 $S$ 去掉 $i$ 之后最近的一个 $1$（如果存在）并加上 $i$。

时间复杂度 $O(2^nnm)$。

Code：

#include<cstdio>
#include<cstring>
const int md=1e9+7,N=20;
inline void upd(int&a){a+=a>>31&md;}
int C,n,m,k,_0[N],_1[N],f[N+1][1<<N];
inline bool check(int id,int S){return(S&_0[id])==0&&(S&_1[id])==_1[id];}
inline int get(int S,int i){
    int T=S&((1<<i)-1);
    if(!T)return(1<<i)|S;
    return(S^(1<<(31-__builtin_clz(T))))|(1<<i);
}
int main(){
    scanf("%d%d%d",&n,&m,&k),--n;
    C=1<<n;
    while(k--){
        int A,B,C;
        scanf("%d%d%d",&A,&B,&C);
        B=n-B;
        (C?_1:_0)[A-1]|=1<<B;
    }
    for(int i=0;i<C;++i)f[n][i]=check(0,i);
    for(int t=1;t<m;++t){
        for(int i=n-1;~i;--i)
        for(int S=0;S<C;++S)if(int d=f[i+1][S]){
            //0
            if(!(_1[t]>>i&1)&&!(S>>i&1))upd(f[i][S]+=d-md);
            //1
            if(!(_0[t]>>i&1)){
                if(S>>i&1)upd(f[i][S]+=d-md);else{
                    int T=get(S,i);
                    upd(f[i][T]+=d-md);
                }
            }
        }
        memcpy(f[n],*f,sizeof*f);
        for(int i=0;i<n;++i)memset(f[i],0,sizeof*f);
    }
    int ans=0;
    for(int i=0;i<C;++i)upd(ans+=f[n][i]-md);
    printf("%d\n",ans);
    return 0;
}