BZOJ2560 (어려움)

사고방식: 뚜렷한 상압 dp가 처음에 쓴 dp는 중복 통계가 나타날 수 있고 하나의 상태 s의 임의적인 연결 집합이 A라고 가정하기 어렵다.그러면 A는 모든 합법적인 방안(Ans)+sigma(어떤 부분은 합법적(즉 어떤 부분은 연결도)의 방안*기타 임의로 연결된 방안)이어야 한다.그러면 최종 답안을 f[i]로 설정하고 임의로 연결(완전 연결)하여 g[i]로 설정할 수 있다.먼저 하나의 기준점 x와 기준점이 연결된 것은 모두 합법적이며 나머지 집합 t=s^(1/************************************************************** Problem: 2560 User: DtenSherlock Language: C++ Result: Accepted Time:1784 ms Memory:2300 kb ****************************************************************/ #include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; const int imax=20; const int kmax=1<<16; const int mod=1e9+7; int n,T; LL a[imax][imax]; LL f[kmax],g[kmax]; void iread() { scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%lld",&a[i][j]); } void iwork() { memset(f,0,sizeof(f)); int Max=(1<1; for(int s=1;s<=Max;s++) { g[s]=1; for(int i=1;i<=n;i++) if(s&(1<1))) { for(int j=i+1;j<=n;j++)// if(s&(1<1))) g[s]=(g[s]*(a[i][j]+1))%mod;// +1 } int nows=0; for(int i=1;i<=n;i++) if(s&(1<1))) { nows=(s^(1<1))); break;} f[s]=g[s]; for(int i=nows;i;i=nows&(i-1))// tips { f[s]=(f[s]-((g[i]*f[s^i])%mod)+mod)%mod; } } printf("%lld
",f[Max]); } int main() { iread(); iwork(); return 0; }