2018HDU多校3-Problem C. Dynamic Graph Matching(hdu 6321)-状压dp

题意：

有n个点，m个操作，操作为增加一条边或删除一条边，每次操作后输出1~n/2个边的匹配个数，k边匹配的定义为：取k条边为一组，这一组边中没有公共点，求能找出多少组

思路：

因为n的范围2~10，数据很小，考虑状压dp，设计dp方程，dp[now][S]表示now状态下，点集为S时，已经匹配的方案数。
对于加边操作，dp[i][S]=dp[i-1][S]+dp[i-1][S-(u,v)]，对应两种情况，即(u,v)没有边的情况，和(u,v)有边的情况
对于减边操作，dp[i][S]=dp[i][S]-dp[i][S-(u,v)]
类似于背包问题的滚动数组，可以将dp数组变成一维，即dp[S]
加边，dp[S]+=dp[S-(u,v)]
减边，dp[S]-=dp[S-(u,v)]

代码：

#include <iostream>
using namespace std;
const int mod=1e9+7;
int cnt[100005];
int dp[100005];
int ans[100005];
void add(int &a,int b)   //加边操作
{
    a+=b;
    if(a>=mod) a-=mod;
}
void sub(int &a,int b)    //减边操作
{
    a-=b;
    if(a<0) a+=mod;
}
int main()
{
    std::ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        int t=1<<n;          //用二进制表示n个点的状态
        for(int i=0;i<t;i++)
        {
            cnt[i]=__builtin_popcount(i);    //计算i的二进制表示中有多少个1
            dp[i]=0;    //初始
        }
        dp[0]=1;   //点集为空时，初始结果为1
        while(m--)
        {
            char a;
            int u,v;
            cin>>a>>u>>v;
            u--,v--;                                         //位移量从0开始计算
            int S=(1<<u)|(1<<v);               //用S表示选择了u，v点的状态
            if(a=='+')
            {
                for(int i=t-1;i>=0;i--)           //遍历全部状态
                {
                    if((i&S)==0)                     //某状态中包含了u，v两点
                    {
                        add(dp[i^S],dp[i]);      //加操作，i^S即表示S-(u,v)，不包含u，v两点的情况
                    }
                }
            }
            if(a=='-')
            {
                for(int i=0;i<t;i++)              //同上，进行减操作
                {
                    if((i&S)==0)
                    {
                        sub(dp[i^S],dp[i]);
                    }
                }
            }
            for(int i=0;i<=n;i++) ans[i]=0;        //初始化
            for(int i=1;i<t;i++)
            {
                add(ans[cnt[i]],dp[i]);            //将最后答案赋给ans，cnt[i]表示i的二进制中1个个数，其意义为当前点集中有边点的个数
            }
            for(int i=2;i<=n;i+=2)                      //因为两个点构成一条边，所以从2开始，每次+2
            {
                if(i==2) cout<<ans[i];           
                else
                    cout<<" "<<ans[i];
            }
            cout<<endl;
        }
    }
    return 0;
}