SGU 476 Coach's Trouble 大数模拟

题目链接：点击打开链接

#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
typedef long long ll;
const int len = 1000000000;
const int L = 700;
const int N = 3001;
struct big {
	int a[L];
	void clear() {
		memset(a,sizeof a);
		a[0] = 1;
	}
	void init() {
		memset(a,sizeof a);
		a[0] = 698;
		a[698] = 1;
	}
	void out() {
		-- a[0];
		while (a[0] - 1 >= 1 && a[a[0]] == 0)
			-- a[0];
		printf("%d",a[a[0]]);
		for (int i = a[0] - 1; i >= 1; --i)
			printf("%09d",a[i]);
		puts("");
	}
};

void sub(big& x,big& y) {
	int v = 0,mx = x.a[0];
	if (mx < y.a[0]) mx = y.a[0];
	for (int i = 1; i <= mx; ++i) {
		x.a[i] += v;
		if (x.a[i] >= y.a[i]) {
			v = 0;
			x.a[i] -= y.a[i];
		} else {
			x.a[i] += len;
			v = -1;
			x.a[i] -= y.a[i];
		}
	}
	
	while (mx - 1 >= 1 && x.a[mx] == 0)
		-- mx;
}

void add(big& x,big& y) {
	ll v = 0;
	int mx = x.a[0];
	if (y.a[0] > mx) mx = y.a[0];
	for (int i = 1; i <= mx; ++i) {
		v += x.a[i] + y.a[i];
		x.a[i] = v % len;
		v /= len;
	}
	while (v > 0) {
		x.a[++mx] = v;
		v /= len;
	}
	x.a[0] = mx;
}

void multi(big& x,int y) {
	ll v = 0;
	int mx = x.a[0];
	for (int i = 1; i <= mx; ++i) {
		v = (ll)x.a[i] * y + v;
		x.a[i] = v % len;
		v /= len;
	}
	while (v > 0) {
		x.a[++mx] = v % len;
		v /= len;
	}
	x.a[0] = mx;
}

big d[N],ans;
int wa[22][3],n,m,mx;

int w[N];
map<int,int> id;
int cnt[N];

void dfs(int idx,int g,int s) {
	if (g & 1) {
		-- cnt[n * 3 - g * 3];
	} else {
		++ cnt[n * 3 - g * 3];
	//	add(ans,d[n * 3 - g * 3]);
	}
	
	if (idx >= 0) {
		int u,ret = s ^ mx,v = (1 << (idx + 1)) - 1;
		ret = ret & v;

		while (ret > 0) {
			u = id[ret & (ret - 1) ^ ret];
			if (u <= idx)
				dfs(u - 1,g + 1,s | w[u]);
			ret = ret& (ret - 1);
		}
	}
}

int main() {
	big vv;
	for (int i = 0; i < 20; ++i)
		id[1 << i] = i;
		
	d[0].clear();
	d[3].clear();
	
	d[0].a[1] = d[3].a[1] = 1;
	for (int i = 6; i <= 3000; i += 3) {
		d[i] = d[i - 3];
		multi(d[i],(i - 1) * (i - 2) / 2);
	}

	while (~scanf("%d%d",&n,&m)) {
		mx = (1 << m) - 1;
		for (int i = 0; i < m; ++i)
			scanf("%d%d%d",&wa[i][0],&wa[i][1],&wa[i][2]);
			
		memset(w,sizeof w);
		for (int i = 0; i < m; ++i) {
			for (int j = i; j < m; ++j) {
				bool done = 1;
				for (int k = 0; done && k < 3; ++k)
					for (int l = 0; done && l < 3; ++l)
						if (wa[i][k] == wa[j][l]) {
							done = 0;
							w[i] |= 1 << j;
							w[j] |= 1 << i;
						}
			}
		}
		memset(cnt,sizeof cnt);
		ans.init();
		dfs(m - 1,0);
		for (int i = 0; i < N; ++i)
			if (cnt[i] != 0) {
				if (cnt[i] > 0) {
					vv = d[i];
					multi(vv,cnt[i]);
					add(ans,vv);
				} else {
					vv = d[i];
					multi(vv,-cnt[i]);
					sub(ans,vv);
				}
			}
		ans.out();
	}
	return 0;
}