【hdu 6321】Dynamic Graph Matching

在这里输入题意

【题解】

DP
设f[i][j]表示前i个操作,已经匹配了的点的状态集合为j的方案数
对于+操作
有两种情况。
1.这条边作为匹配的边
2.这条边没有作为匹配边
f[i][j] = f[i-1][j-(u,v)] + f[i-1][j]
作为匹配边,转化一下就是这条边的两个点连上了。也即被匹配了。
对于-操作
考虑前i-1个操作。
会发现+操作的先后顺序不影响前i-1个操作之后的结果。
因此我们干脆就认为第i-1个操作就是和- u,v对应的+ u,v就好了
因此我们只需将$f[i-1][j]-f[i-1][j-(u,v)]$的值赋值给f[i][j]即可。
最后统计匹配数的方案就好了
j这个状态有几个匹配要预处理出来。

【代码】

#include<bits/stdc++.h>

using namespace  std;

#define ll long long

#define pb push_back

#define inf 2099999999

#define mod 1000000007

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define rep1(i,a,b) for(int i=a;i>=b;i--)

const int M = 1024;

int T,n,m;

int f[M+10],pre[12];

int cnt[6],pre2[M+10];

char s[5];

int main()

{

	#ifdef LOCAL_DEFINE

	    freopen("rush_in.txt", "r", stdin);

	#endif

    scanf("%d",&T);

    pre[0] = 1;

    rep(i,1,10) pre[i] = pre[i-1]*2;

    for (int i = 0;i < M;i++){

        int x = i,cur = 0;

        while (x>0){

            cur+=(x%2);

            x/=2;

        }

        if (cur%2==0) pre2[i] = cur/2;

    }

    while(T--){

        scanf("%d%d",&n,&m);

        memset(f,0,sizeof f);

        f[0] = 1;

        for (int i = 1;i <= m;i++){

            int x,y;

            scanf("%s",s);scanf("%d%d",&x,&y);

            x--;y--;

            if (s[0]=='+'){

                for (int j = pre[n]-1;j >=0;j--)

                    if (((j&pre[x])>0) && ((j&pre[y])>0)  ){

                        int jj = j ^ pre[x];

                        jj = jj ^ pre[y];

                        f[j] = f[j] + f[jj];

                        if (f[j]>mod) f[j]-=mod;

                    }

            }else{

                for (int j = pre[n]-1;j >= 0;j--){

                    if (((j&pre[x])>0) && ((j&pre[y])>0)){

                        int jj = j^pre[x];

                        jj = jj^pre[y];

                        f[j] = f[j]-f[jj]+mod;

                        if (f[j]>mod) f[j]-=mod;

                    }

                }

            }

            memset(cnt,0,sizeof cnt);

            for (int j = 0;j < pre[n];j++)

                cnt[pre2[j]] = (cnt[pre2[j]] + f[j])%mod;

            for (int i = 1;i <= n/2;i++) {

                if (i!=1) putchar(' ');printf("%d",cnt[i]);

            }

            puts("");

        }

    }

    return 0;

}

巴特西

【hdu 6321】Dynamic Graph Matching

最新文章

热门文章