Adore 题解【DP】【状态压缩】

点击量：200

    奇怪的状压+神奇的转移。

目录

题目背景

小\(\text{w}\)偶然间看到了一个\(\text{DAG}\)。

 

题目描述

这个\(\text{DAG}\)有\(m\)层，第一层只有⼀个源点，最后一层只有一个汇点，剩下的每一层都有\(k\)个节点。

 

现在小\(\text{w}\)每次可以取反第\(i(1<i<n-1)\)层和第\(i+1\)层之间的连边。也就是把原本从\((i,k_1)\)连到\((i+1,k_2)\)的边，变成从\((i,k_2)\)连到\((i+1,k_1)\)。

 

请问他有多少种取反的方案，把从源点到汇点的路径数变成偶数条？

 

答案对\(998244353\)取模。

 

输入输出格式

输入格式：

一行两个整数\(m,k\)。

 

接下来\(m-1\)行, 第一行和最后一行有\(k\)个整数\(0\)或\(1\)，剩下每行有\(k^2\)个整数\(0\)或\(1\)，第\((j-1)\times k+t\)个整数表示\((i,j)\)到\((i+1,t)\)有没有边。

输出格式：

一行一个整数表示答案。

 

输入输出样例

输入样例#1：

5 3
1 0 1
0 1 0 1 1 0 0 0 1
0 1 1 1 0 0 0 1 1
0 1 1

输出样例#1：

4

说明

\(20\%\)的数据满足\(n\le 10,k\le 2\)。

\(40\%\)的数据满足\(n\le 10^3,k\le 2\)。

\(60\%\)的数据满足\(m\le 10^3, k\le 5\)。

\(100\%\)的数据满足\(4\le m\le 10^4,k\le 10\)。

题解：

    这个题最重要的一点是理解题意，当时以为答案是\(2^{n-3}\)或\(2^{n-3}-1\)加特判，后来发现是自己理解错了。

    题目中告诉我们，“把原本从\((i,k_1)\)连到\((i+1,k_2)\)的边，变成从\((i,k_2)\)连到\((i+1,k_1)\)”。因此得到的效果是这样的：

    也就是说，在输入过程中，第\(i\)行输入了\(i-1\)行指向第\(i\)行的边，正常遍历顺序是\(i:1\ \text{to}\ n,j:1\ \text{to}\ n\)，那么取反之后就是\(j:1\ \text{to}\ n,i:1\ \text{to}\ n\)。这样的话每个点的出边指向的点是可以状压的（存入边常数会比较大，后面会提），但是这个题要求路径种类数为偶数。

    偶数的话可以用二进制存，类似\(0+0=0,0+1=1,1+0=1,1+1=0\)，我们就可以考虑同时把方案数状压，想到这里可以把上下两个状压联系起来。枚举作为\(1\)的位置（\(0\)即偶数，不会做出贡献），然后直接拿出边异或转移出去的状态，最终得到的状态为1的位所表示的位置，方案数为奇数。这样递推进行状压DP即可。

    上面提到了不存入边，此时存出边跟入边是刷表和填表的区别，如果填表，就要考虑转移进来的是奇数还是偶数，这时要查询状压状态下有多少个\(1\)，可以预处理popcount，但是这样数组维度多，常数就会大。而用出边刷表就可以直接二进制异或，也就是对每一位分别做加法，满\(2\)变\(0\)，减小常数的幅度很大。

    因为第一层和最后一层不能取反，我们令初始状态为第二层，最终状态为倒数第二层即可。

Code：

#include<cstdio>
#include<cstring>
#define lowbit(x) (x&(-x))
int f[10010][1024];
bool con[10010][11][11];
int ot1[10010][11];//最后一位表示是否取反
int ot0[10010][11];
int popcount(int x)
{
    int cnt=0;
    while(x)
    {
        ++cnt;
        x-=lowbit(x);
    }
    return cnt;
}
int ppc[1025];
int main()
{
    for(int i=1;i<=1024;++i)
        ppc[i]=popcount(i);
    int n,k,u;
    scanf("%d%d",&n,&k);
    int st=0;
    for(int i=1;i<=k;++i)
    {
        scanf("%d",&u);
        st|=(u<<(i-1));
    }
    for(int i=2;i<n-1;++i)
    {
        for(int p=1;p<=k;++p)
            for(int q=1;q<=k;++q)
            {
                scanf("%d",&u);
                con[i][p][q]=u;
            }
    }
    int fi=0;
    for(int i=1;i<=k;++i)
    {
        scanf("%d",&u);
        fi|=(u<<(i-1));
    }
    for(int i=2;i<n;++i)
        for(int p=1;p<=k;++p)
            for(int q=1;q<=k;++q)
            {
                if(con[i][p][q])
                    ot0[i][p]|=(1<<(q-1));//状压出边
                if(con[i][q][p])
                    ot1[i][p]|=(1<<(q-1));
            }
    f[2][st]=1;
    for(int i=2;i<n-1;++i)
    {
        for(register int j=0;j<(1<<k);++j)
        {
            int sta[2]={0,0};
            for(int t=1;t<=k;++t)
            {
                if((j>>(t-1))&1)
                {
                    sta[0]^=ot0[i][t];
                    sta[1]^=ot1[i][t];
                }
            }
            f[i+1][sta[0]]=(f[i+1][sta[0]]+f[i][j])%998244353;
            f[i+1][sta[1]]=(f[i+1][sta[1]]+f[i][j])%998244353;
        }
    }
    long long ans=0;
    for(int i=0;i<(1<<k);++i)
        if(!(ppc[i&fi]&1))//统计答案要求路径数也为2
            ans=(ans+f[n-1][i])%998244353;
    printf("%lld\n",ans);
    return 0;
}