给出一些点集，然后对于每一次要求给出的这些点集里的1,2,3,4,5,6....n/2的匹配数，
dp[i][j] 表示到第i次操作里点集为j的匹配数，然后我每次加入一条边u-v，我的状态就是
dp[i][j] = dp[i-1][j] + dp[i-1][（不含u,v）的j]，删除就是dp[i][j] = dp[i-1][j] - dp[i-1][（不含u,v）的j]
一个匹配就是两个点，所以2*i个点的答案就是匹配为i的答案。
然后可以减去一维，变成一维的dp，然后在取模一下就可以了
#include<map>
#include<set>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lowbit(x) (x & (-x)) typedef unsigned long long int ull;
typedef long long int ll;
const double pi = 4.0*atan(1.0);
const int inf = 0x3f3f3f3f;
const int maxn = ;
const int maxm = ;
const int mod = 1e9+;
using namespace std; int n, m, tol, T;
int dp[maxn];
int cnt[maxn];
int ans[]; void init() {
memset(dp, , sizeof dp);
} int calc(int x) {
int ans = ;
while(x) {
if(x & ) ans++;
x >>= ;
}
return ans;
} void handle() {
for(int i=; i<=(<<); i++) {
cnt[i] = calc(i);
}
} int main() {
handle();
scanf("%d", &T);
while(T--) {
init();
scanf("%d%d", &n, &m);
dp[] = ;
char s[];
while(m--) {
memset(ans, , sizeof ans);
int u, v;
scanf("%s%d%d", s, &u, &v);
u--, v--;
int y = (<<u) + (<<v);
if(s[] == '+') {
for(int i=(<<n)-; i>=; i--) {
if((i&(<<u)) && (i&(<<v))) {
dp[i] += dp[i-y];
dp[i] %= mod;
}
}
} else {
for(int i=; i<(<<n); i++) {
if((i&(<<u)) && (i&(<<v))) {
dp[i] -= dp[i-y];
dp[i] = (dp[i] % mod + mod) % mod;
}
}
}
for(int i=; i<(<<n); i++) {
ans[cnt[i]] += dp[i];
ans[cnt[i]] = (ans[cnt[i]] % mod + mod) % mod;
}
for(int i=; i<=n; i+=) printf("%d%c", ans[i] % mod, i==n ? '\n' : ' ');
}
}
return ;
}