HDU 6321 Problem C. Dynamic Graph Matching [상압]

제목의 뜻

n개의 점을 준 그림은 처음에는 끝이 없고 그림에 일치하는 변을 설정할 수 있다(그 두 단점은 한 변만 연결할 수 있다). 모두 m회 조작이 있고 매번 조작에 한 변을 추가한다. 매번 조작 후에 일치하는 변의 총수는 1~n/2의 방안 수를 구한다.

문제풀이

dp[i]가 현재 점용점의 상황을 나타내는 이진 형식을 정의합니다. 가변이라면 전이 방정식은

dp[state|f[x]|f[y]]+=dp[state];

가령 가장자리를 삭제한다면

dp[state|f[x]|f[y]]-=dp[state];

AC 코드

#include
#include
#define N 100005
#define P pair
using namespace std;
typedef long long ll;
const int M=1e9+7;
ll dp[1200],sum[6],s[1200],ss[1200];
int f[11],n,x,y,d,k;
ll Mod(ll x,ll y)
{
    if(x>=y)x-=y;
    if(x<0)x+=y;
    return x;
}
void dfs(int p,int state)
{
    if(p>=n)
    {
        if(s[state]&1)return ;
        k=state|f[x]|f[y];
        sum[ss[state]]=Mod(sum[ss[state]]-dp[k],M);
        dp[k]=Mod(dp[k]+d*dp[state],M);
        sum[ss[state]]=Mod(sum[ss[state]]+dp[k],M);
        return;
    }
    if(p!=x&&p!=y)dfs(p+1,state|f[p]);
    dfs(p+1,state);
}
int main()
{
    for(int i=0;i1<<10);i++)
        for(int j=0;j<10;j++)
            if(i&(1<s[i]++;
    for(int i=0;i1<<10);i++)
        ss[i]=s[i]/2+1;
    f[0]=1;
    for(int i=1;i<=10;i++)
        f[i]=f[i-1]*2;
    int t,m;
    scanf("%d",&t);
    for(;t;t--)
    {
        scanf("%d%d",&n,&m);
        memset(dp,0,sizeof(dp));
        memset(sum,0,sizeof(sum));
        dp[0]=1;
        char c[5];
        while(m--)
        {
            scanf("%s%d%d",c,&x,&y);
            x--;y--;
            d=c[0]=='+'?1:-1;
            dfs(0,0);
            for(int i=1;i2;i++)
                printf("%lld ",sum[i]);
            printf("%lld
",sum[n/2]);
        }
    }
    return 0;
}