http://acm.hdu.edu.cn/showproblem.php?pid=6321

Problem Description
In the mathematical discipline of graph theory, a matching in a graph is a set of edges without common vertices.
You are given an undirected graph with n vertices, labeled by 1,2,…,n. Initially the graph has no edges.
There are 2 kinds of operations :
+u v, add an edge (u,v) into the graph, multiple edges between same pair of vertices are allowed.
-u v, remove an edge (u,v), it is guaranteed that there are at least one such edge in the graph.
Your task is to compute the number of matchings with exactly k edges after each operation for k=1,2,3,…,n2. Note that multiple edges between same pair of vertices are considered different.

题意：n（<=10）个点，m（3万）次修改，每次增或删一条边，并询问当前恰好k条边（k<=n/2）的匹配数。
思路：状压，设 f ( s ) ： 覆 盖 点 为 s 的 匹 配 数 f(s)：覆盖点为s的匹配数 f(s)：覆盖点为s的匹配数，在之前图的基础上，考虑加一条边的影响，那么就考虑使用这条边连两点u，v，然后加上剩余的连法，即 f [ s ] + = f [ s f[s]+=f[s f[s]+=f[s x o r ( 1 &lt; &lt; u ) x o r ( 1 &lt; &lt; v ) ] xor(1&lt;&lt;u) xor (1&lt;&lt;v)] xor(1<<u)xor(1<<v)]，减边也是一样的道理。
注意从后往前更新，滚动数组。
复杂度 O ( T ∗ m ∗ 2 n ) O(T*m*2^n) O(T∗m∗2n)

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007

int T,n,m;
int f[1<<10],cnt[1<<10],ans[6];

void init()
{
	for(int s=0;s<(1<<10);s++)
	{
		int i=s,c=0;
		while(i)
		{	
			if(i&1)c++;
			i>>=1;
		}
		cnt[s]=c;
	}
}

int main()
{
	///freopen("input.in","r",stdin);
	cin>>T;
	init();
	while(T--)
	{
		cin>>n>>m;
		memset(f,0,sizeof(f));
		f[0]=1;
		while(m--)
		{
			char op[5];
			int u,v;
			cin>>op>>u>>v;
			u--;v--;
			for(int s=(1<<n)-1;s>=0;s--)if((s&(1<<u))&&(s&(1<<v)))
			{
				if(op[0]=='+')f[s]=(f[s]+f[s^(1<<u)^(1<<v)])%mod;
				else f[s]=(f[s]-f[s^(1<<u)^(1<<v)]+mod)%mod;
			}
			memset(ans,0,sizeof(ans));
			for(int s=1;s<(1<<n);s++)ans[cnt[s]/2]+=f[s],ans[cnt[s]/2]%=mod;
			printf("%d",ans[1]);
			for(int i=2;i<=n/2;i++)printf(" %d",ans[i]);
			putchar('\n');
		}
	}
	return 0;
}