题意：

定义图的匹配是一组任意两边都没有公共顶点的边集，有n个点，现在有两种类型的操作m个：

$+ u\ v$：在u和v之间加一条边，

$- u\ v$：删去u和v之间的边，

问每次操作之后边集中有$1,2,3,···,\frac{n}{2}$条边的边集有几个。

其中$1≤T≤10,2≤n≤10,n\ mod\ 2=0,1≤m≤30000$。

思路：

由n的范围可以想到要状压，

考虑$dp[i][j]$：经过i次操作之后，j集合的点已经匹配的方案数。

比如j为0011的时候，只有两个点，边集只能有一条边，1111的时候，因为是匹配，表示边集有两条边。

加边的时候$dp[i][j]=dp[i-1][j]+dp[i-1][j-u-v]$，可以写成一维的，从大到小遍历j。

对于删边，因为之前加边的顺序对于删边是没有关系的，所以可以看作i-1的时候刚把这条边加上，所以将加边操作倒过来，即从小到大遍历j，$dp[i][j]=dp[i][j]-dp[j-u-v]$。

刚开始的时候连题解都看不懂啊…把标程dp中的前后状态输出来才懂啊…主要是对题目的这个匹配的没有很好地理解…

__builtin_popcount函数：返回一个数的二进制形式中有多少个1。

代码：

typedef long long ll;
char a[5];
int cnt[1200];
ll dp[1200];
ll ans[1200];
void trans(int x)
{
    for(int i=0;i<4;i++)
    {
        printf("%d",x%2);
        x/=2;
    }
    printf("\n");
}
int main()
{
    int t,n,x,y,m;
    scanf("%d",&t);
    for(int i=0; i<(1<<10); i++)
        cnt[i]=__builtin_popcount(i);
    /*for(int i=0;i<(1<<4);i++)
        printf("%d\n",cnt[i]);*/
    while(t--)
    {
        scanf("%d%d",&n,&m);
        int tot=1<<n;
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        while(m--)
        {
            scanf("%s%d%d",a,&x,&y);
            x--;y--;
            int temp=1<<x|1<<y;
            //printf("temp:");trans(temp);
            if(a[0]=='+')
            {
                for(int i=tot-1; i>=0; i--)
                {
                    if(!(temp&i))//i中没有u和v
                    {
                        //printf("before:");trans(i);
                        dp[i|temp]=(dp[i|temp]+dp[i])%MOD;
                        //printf("after:");trans(i|temp);
                        //printf("%lld->%lld\n",dp[i],dp[i|temp]);
                    }
                }
            }
            else
            {
                for(int i=0;i<tot;i++)
                {
                    if(!(temp&i))
                        dp[i|temp]=(dp[i|temp]-dp[i]+MOD)%MOD;
                }
            }
            memset(ans,0,sizeof(ans));
            for(int i=0;i<tot;i++)
                ans[cnt[i]]=(ans[cnt[i]]+dp[i])%MOD;
            printf("%lld",ans[2]);
            for(int i=4;i<=n;i+=2)
                printf(" %lld",ans[i]);
            printf("\n");
        }
    }
    return 0;
}