Submission #44990689

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN = 15;

int n,m;

int ok[1<<MAXN];

queue<int>q[MAXN][MAXN];
vector<int>e[1<<MAXN];

ll dp[1<<MAXN],lst;

void calc(int x){
	//对x的所有超集做dp
	vector<int>S;
	for(int u = x;u != ((1<<n)-1);u = (u+1) | x){
		S.push_back(u);
	}
	S.push_back((1<<n)-1);
	sort(S.begin(),S.end());
	for(auto u : S){
		if(!ok[u])continue;
		dp[u] = 0;
		rep(i,0,n-1)if(u>>i&1)dp[u] += dp[u^(1<<i)];
	}
}

void add(int mask){
	rep(i,0,n-1)if(!(mask>>i&1))rep(j,i+1,n-1)if(mask>>j&1){
		q[i][j].push(mask);
	}
}

int main(){
	ios::sync_with_stdio(false);

	cin>>n>>m;

	rep(i,0,(1<<n)-1)e[i].push_back(i);

	rep(i,0,n){
		int mask = 0;
		rep(j,0,i-1)mask |= (1<<j);
		ok[mask] = dp[mask] = 1;
	}
	rep(mask,0,(1<<n)-1){
		add(mask);
	}

	lst = 1;

	rep(i,1,m){
		int u,v;cin>>u>>v;
		u = (u + lst)%n,v = (v + lst*2)%n;
		if(u>v)swap(u,v);

		while(q[u][v].size()){
			int S = q[u][v].front();q[u][v].pop();
			if(e[S].empty())continue;

			int X = S^(1<<u)^(1<<v);
			for(auto T : e[S]){
				int X = S^(1<<u)^(1<<v);
				e[X].push_back(T);

				if(ok[X]==1 && !ok[T]){
					ok[T] = 2;
					calc(T);
				}
			}
			e[S].clear();
			add(X);
		}
		

		lst = dp[(1<<n)-1];
		cout<<lst<<"\n";
	}

    return 0;
}

Submission Info

Judge Result