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;
}

BZOJ2560 (어려움)

좋은 웹페이지 즐겨찾기