题解 P4892 【GodFly的寻宝之旅】

· · 题解

典型的状压dp

状压dp的精髓就在于去压缩状态！然后通过一系列位运算让一个int变量实现一个约20位的数组的功能。

蒟蒻写的状压dp总结顺便安利一波博客

现在回到正题，n<=18是明显的状压标志，我们用f[i][j]表示当前点为i，走过的点集合为j时的方案数。

上一篇题解已经把状态转移说的很清楚了，这里就不再赘述。

有人可能会问：题目中不是要求滑稽基态或者对偶态的情况数量吗？按照正常逻辑应该在后面再加上一维[0/1]，来记录滑稽态/对偶态的情况数量。（事实上出题人的官方题解也是开了三维数组的）

事实上只需要开两维就行了。为什么呢？

@yuyue大佬告诉我：“这题其实有规律的：一条路径无论顺序如何w始终相等”（有兴趣的可以去证明一下，打表也是可以的）

%%%太巨了@yuyue 巨佬

有了这个结论，就可以直接通过最后的状态算出滑稽/对偶态。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#define mod 19260817
#define ll long long
using namespace std;

int n,m,c;
int a[20][20];
ll f[20][1<<18+2];//当前点i状态为j 
ll ans;
//判断状态的w值
bool pd(int v){
    int sum=0,w=0;
    for(int o=1;o<=n;o++)
    if(v&(1<<o-1))
    w=(w+sum*o)%2,sum=(sum+o)%2;
    return w%2==c;
} 

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
       int x,y;
       scanf("%d%d",&x,&y);
       if(x!=y)
       a[x][y]++,a[y][x]++; 
    }
    scanf("%d",&c);
    f[1][1]=1;
    for(int i=1;i<(1<<n);i++)//枚举所有状态
    for(int j=1;j<=n;j++)//枚举to点
    if((1<<j-1)&i)
    for(int k=1;k<=n;k++)//枚举fro点
    if((1<<k-1)&i&&k!=j&&a[j][k])
    f[j][i]=(f[j][i]*1ll+1ll*a[j][k]*f[k][i-(1<<j-1)])%mod;
    for(int i=1;i<(1<<n);i++)
    if((i&1)&&(i&1<<n-1))
    if(pd(i))
    ans=(ans+f[n][i])%mod;
    cout<<ans;
    return 0; 
}