记录编号	84923	评测结果	AAAAAAAAAA
题目名称	[NOI 1996]三角形灯塔	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.034 s
提交时间	2013-12-21 20:40:51	内存使用	0.23 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<iomanip>
using namespace std;
const int SIZEN=51;
typedef long long ll;
int N,P;
ll notation[SIZEN][SIZEN]={0};//二进制表示
ll pow2[60]={1};
int ps[SIZEN]={0};//P个灯的状态
ll pn[SIZEN]={0};//P个灯的表示
int getdig(ll x,int k){//第k位是2^k-1
	return (x&pow2[(k-1)])>>(k-1);
}
void changedig(ll &x,int k,int t){//x的第k位变成t
	if(t) x|=pow2[k-1];
	else x&=(~pow2[k-1]);
}
void printdig(ll x){//调试接口,输出x表示的状态
	for(int i=1;i<=N;i++) cout<<getdig(x,i);
}
void solve(void){
	int i,j,k;
	int a,b;
	ll ans=0;
	for(j=1;j<=P;j++){//P个方程至多消去P个未知数
		for(k=j;k<=N;k++){
			for(i=j;i<=P;i++){
				if(i<=P&&getdig(pn[i],k)) goto OF;
			}
		}
		OF:;
		if(i==P+1) continue;//无效元素
		ans++;
		if(k!=j){//交换列
			for(i=1;i<=P;i++){
				a=getdig(pn[i],j),b=getdig(pn[i],k);
				changedig(pn[i],j,b);
				changedig(pn[i],k,a);
			}
		}
		if(i!=j) swap(pn[i],pn[j]);swap(ps[i],ps[j]);//交换行
		for(i=1;i<=P;i++){
			if(i==j||!getdig(pn[i],j)) continue;
			pn[i]^=pn[j];
			ps[i]^=ps[j];
		}
	}
	for(i=1;i<=P;i++){
		if(!pn[i]&&ps[i]){
			printf("No Answer!\n");
			return;
		}
	}
	ans=N-ans;
	ans=pow2[ans];
	cout<<ans<<endl;
}
void getnotation(void){
	int i,j;
	for(i=1;i<=N;i++) notation[N][i]=pow2[i-1];//只有i起作用
	for(i=N-1;i>=1;i--){
		for(j=1;j<=i;j++){
			notation[i][j]=(notation[i+1][j]^notation[i+1][j+1]);
		}
	}
}
void init(void){
	for(int i=1;i<=51;i++) pow2[i]=pow2[i-1]*2;
	scanf("%d",&N);
	getnotation();
	P=0;
	int x,y,s;
	while(true){
		scanf("%d%d%d",&x,&y,&s);
		if(!(x||y||s)) break;
		P++;
		pn[P]=notation[x][y];
		ps[P]=s;
	};
}
int main(){
	freopen("lighthouse.in","r",stdin);
	freopen("lighthouse.out","w",stdout);
	init();
	solve();
	return 0;
}