题解 AT2669【[AGC017F] Zigzag】

· · 题解

可以通过的暴力做法。

令 f_{i,j} 表示第 i 条折线的状态是 j 的方案数。“某些折线的第 i 位只能填 a_i”之类的限制是简单处理的，现在唯一的问题就在于不同 i 间的转移。

考虑某一条折线。我们要计算 其下方所有折线的 f 之和。

        /\
 /\    /  \    /
/  \  /    \/\/
    \/         
123456789ABCDEFG

如上图所示的一条折线。则，其有如下几个后继态：

我们考虑容斥。则 f_{i,j} 等于 f_{i-1,j} 加上扳下去一个角的方案数，减去扳下去两个的方案数，加上三个……

暴力枚举哪些角被扳下去。一个角在 01 态中对应了“10”的表达，扳下去就意味着把 10 变成 01。特别地，最后一位如果是 1 则也被看作是“角”。

口胡一下复杂度：一个有 i 个“角”的态，会对答案的贡献是 2^i。枚举有 i 个角，然后剩下的 01 插空放，可以得到复杂度是

\sum\limits_{i=0}^{n/2}2^i\sum\limits_{j=0}^{n-2i}\dbinom{j+i}{i}\dbinom{n-2i-j+i}{i}

但是分析理论复杂度没啥用处（其实是这个家伙不会分析）。实测 n=20 时，一次转移中，循环执行了 22095249 次，和 n2^n 的复杂度不相伯仲。

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
void ADD(int&x,int y){if((x+=y)>=mod)x-=mod;}
int n,m,K,m0[30],m1[30],f[1<<20],res,pc[1<<20];
int main(){
    scanf("%d%d%d",&n,&m,&K),n--;
    for(int i=1,x,y,z;i<=K;i++)
        scanf("%d%d%d",&x,&y,&z),(z==1?m1:m0)[x]|=1<<n-y;
    for(int i=1;i<(1<<n);i++)pc[i]=pc[i>>1]+(i&1);
    for(int i=0;i<(1<<n);i++)
        if((i&m1[1])==m1[1]&&!(i&m0[1]))f[i]=1;
    // for(int i=0;i<(1<<n);i++)printf("%d ",f[i]);puts("");
    for(int _=2;_<=m;_++){
        for(int j=0;j<(1<<n);j++){
            int U=0;
            if(j&1)U|=1;
            for(int i=1;i<n;i++)if((j&(1<<i))&&!(j&(1<<i-1)))
                U|=1<<i;
            for(int u=U;u;u=(u-1)&U){
                int v=(u|u>>1)&((1<<n)-1);
                if(pc[u]&1)ADD(f[j],f[j^v]);
                else ADD(f[j],mod-f[j^v]);
            }
        }
        for(int j=0;j<(1<<n);j++)if((j&m1[_])!=m1[_]||(j&m0[_]))f[j]=0;
    }
    // for(int i=0;i<(1<<n);i++)printf("%d ",f[i]);puts("");
    for(int i=0;i<(1<<n);i++)(res+=f[i])%=mod;
    printf("%d\n",res);
    return 0;
}