[bzoj2560]串珠子

我的状压dp大概是废掉了

这道题考虑容斥，然后g[i]记总方案，f[i]记答案

然后我们枚举子集 j ，f [ i ] = f [ i ] - sigma { f [ i^j] * g [ j ] }

注意不能算最前一位进来（相当于硬点一位在左边）

#include<bits/stdc++.h>using namespace std;const int N=20;typedef long long ll;ll mod=1e9+7;ll f[200005];ll g[200005];int mp[N][N];int n;int main(){scanf("%d",&n);for(int i=0;i<n;i++){for(int j=0;j<n;j++){scanf("%d",&mp[i][j]);}}f[0]=1;for(int st=1;st<1<<n;st++){g[st]=1;for(int j=0;j<n;j++)if(st&(1<<j))for(int k=j+1;k<n;k++)if(st&(1<<k)){g[st]=g[st]*(mp[j][k]+1)%mod;}f[st]=g[st];int now=0;for(int j=n-1;j>=0;j--)if(st&(1<<j)){now=j;break;}now=st^(1<<now);for(int j=now;j;j=(j-1)&now){f[st]=(f[st]-f[st^j]*g[j]%mod+mod)%mod;}}printf("%lld\n",f[(1<<n)-1]);}

如果觉得《[bzoj2560] 串珠子》对你有帮助，请点赞、收藏，并留下你的观点哦！