bzoj 2560ビーズ状圧dp反発
2974 ワード
f[i]が集合iがつながっていることを示すシナリオ数を設定し,叱ればよい.複雑度O(3 n)
#include
using namespace std;
#define ll long long
#define mod 1000000007
int n;
int c[21][21],f[(1<<16)+10],sum[(1<<16)+10];
int main()
{
//freopen("tt.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&c[i][j]);
for(int i=1;i<1<sum[i]=1;
for(int j=0;jif(i>>j&1)
for(int k=j;kif(i>>k&1)
sum[i]=(ll)sum[i]*(c[j+1][k+1]+1)%mod;
}
for(int i=1;i<1<sum[i];
int t=i&-i;
for(int j=i;j;j=(j-1)&i)if(~j&t)
f[i]=(f[i]-(ll)f[i-j]*sum[j]%mod+mod)%mod;
}
printf("%d
",f[(1<1]);
return 0;
}