Luogu P4892 GodFly的寻宝之旅【状压dp】By cellur925

程序员家振技术 2022年11月9日

0 收藏 822 点赞 3,203 浏览 1368 个字

又是一道状压+计数类好题hh（真香）。数据范围非常友好，告诉我们$n<=18$，非常符合状压的性质。

其实感觉和$Hamilton$路径那题还是有些相似的，我们可以类似地设计出状态：$f[i][j][w]$表示当前状态为$i$，现在位于$j$点，体力耗费为$w$（$w$只有两种可能）的方案数。

我们考虑转移的时候向之后的状态转移，设$i$为当前的状态，$j$为上一个最后落在的位置，$k$是这一次最后落在的位置。因为有滑稽态&&奇偶态两种，所以有两种转移。因为边数在$1e5$的范围内，所以肯定是个稠密图，有很多很多重边，又因为本题数据范围很小，不妨直接用邻接矩阵存下两点间有多少重边。转移的时候就可以直接从上一方案乘上重边数转移过来。又注意到题中的$sum()$其实是可以预处理出来的，所以我们就先搞出来降低复杂度。

最后我们得到了转移方程：

(f[i|(1<<(k-1))][k][(0+k*st[i])%2]+=1ll*f[i][j][0]*cnt[k][j])%=moder;
(f[i|(1<<(k-1))][k][(1+k*st[i])%2]+=1ll*f[i][j][1]*cnt[k][j])%=moder;

$Code$

#include<cstdio>
#include<algorithm>
#define maxn 300000using namespace std;
typedef long long ll;
const ll moder=19260817;int n,m,opt,fake;
ll ans,st[maxn],f[maxn][20][3];
int cnt[30][30];int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x=0,y=0;
scanf("%d%d",&x,&y);
cnt[x][y]++,cnt[y][x]++;
}
scanf("%d",&opt);
fake=(1<<n)-1;
for(int i=0;i<=fake;i++)
for(int j=0;j<n;j++)
if(i&(1<<j)) st[i]+=j+1;
f[1][1][0]=1;
for(int i=0;i<=fake;i++)
for(int j=1;j<=n;j++)
{//枚举上一个位置
if(!(i&(1<<(j-1)))) continue;
for(int k=1;k<=n;k++)
{//枚举当前落到的位置
if(i&(1<<(k-1))) continue;
(f[i|(1<<(k-1))][k][(0+k*st[i])%2]+=1ll*f[i][j][0]*cnt[k][j])%=moder;
(f[i|(1<<(k-1))][k][(1+k*st[i])%2]+=1ll*f[i][j][1]*cnt[k][j])%=moder;
}
}
for(int i=0;i<=fake;i++)
(ans+=f[i][n][opt])%=moder;
printf("%lld\n",ans);
return 0;
}