hdu6321 C. Dynamic Graph Matching

问题描述：
给定一个 n 个点的无向图，m 次加边或者删边操作。在每次操作后统计有多少个匹配包含 k = 1, 2, …,n/2 条边。
2 ≤ n ≤ 10, 1 ≤ m ≤ 30000。

官方解释

队友的代码，注释蛮详细的。。。

/** http://acm.hdu.edu.cn/showproblem.php?pid=6321
  * 题意：给n个点，求从中取没有公共点的几条边的方案数目
  * 动态添加或删除图中的边，每次改动，都依次输出取1到n/2条边的方案数
  * 思路：n小于等于10，不一定是允许暴搜，其实是暗示状压dp，
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
const int N = 1025;
const int M = 12;

int Kase,n,q,u,v,mxs;
int dp[N][M];
int cnt[N];//统计cnt[state]有几个1（点
char op[2];


int main() {
    for(int i=1;i<N;i++)
        cnt[i]=cnt[i>>1]+(i&1);
        //预处理统计所有状态有几个点，也用了dp的思维

    scanf("%d",&Kase);
    while(Kase--){
        scanf("%d %d",&n,&q);
        memset(dp,0,sizeof dp);
        mxs=(1<<n)-1;

        for(int i=0;i<=mxs;i++)
            dp[i][0]=1;

        while(q--){
            scanf("%s%d%d",op,&u,&v);
            u--,v--;
            int uv=(1<<u)|(1<<v);//把u和v点转换成二进制数uv，表示含有u和v点的状态

            for(int s=mxs;s>=0;s--){
                //从满状态开始更新，从点多到点少更新，避免重复累加
                if((s&uv)!=uv)continue;//不包括u和v点的状态跳过不更新

                for(int j=1;j<=cnt[s];j++){//这里和方向应该没关系，实际情况好像反过来会慢一些
                    dp[s][j]+=(op[0]=='+')?dp[s^uv][j-1]:(mod-dp[s^uv][j-1]);
                        //状态转移方程，当前状态（包括uv点的集合s，取j条边的的方案数）
                        //等于所有不包括uv点的集合，取j-1条边的方案数转移而来

                    if(dp[s][j]>=mod)dp[s][j]-=mod;
                       //这题会卡取模，以防万一用减法避免
                }
            }

            for(int i=1;i<=n/2;i++)
                printf("%d%c",dp[mxs][i],i==n/2?'\n':' ');
        }
    }
    return 0;
}
/*
1
4 8
+ 1 2
+ 3 4
+ 1 3
+ 2 4
- 1 2
- 3 4
+ 1 2
+ 3 4
*/