CODE FESTIVAL 2015 Exhibition B: TRAX

流行のゲーム。

3つのパターンに場合わけして頑張って数えるだけだけど、白と赤がついているせいでうまく数えにくい。
多分こういう系(2次元のグリッドに変なのを並べる方法を数える)の数え上げ得意なんだろうと思う

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
long long mod=1000000007;
int p[110000];
int q[110000];
int r[110000];
int s[110000];
int t[110000];
long long dp[110000][5][2];
long long dp2[110000][5];
int L[2][110000];
int R[2][110000];
int keyL[110000];
int keyR[110000];
vector<int>v[2][110000];
vector<pair<int,int> > v2[110000];
int main(){
	int a,b,c;scanf("%d%d%d",&a,&b,&c);
	for(int i=0;i<c;i++){
		scanf("%d%d%d",p+i,q+i,r+i);
		p[i]--;
		q[i]--;
		r[i]--;
		s[q[i]]|=(1<<(r[i]^(p[i]%2*2)));
		t[p[i]]|=(1<<(r[i]^(q[i]%2*2)));
		v[r[i]%2][q[i]].push_back(p[i]);
		v2[q[i]].push_back(make_pair(p[i],r[i]));
	}
	long long ret=0;
	bool dame=false;
	for(int i=0;i<b;i++){
		if(__builtin_popcount(s[i])>1)dame=true;
	}
	if(!dame){
		if(s[0]){
			for(int i=0;i<4;i++)if(s[0]==(1<<i))dp[1][i][0]=1;
		}else{
			for(int i=0;i<4;i++)dp[1][i][0]=1;
		}
		for(int i=1;i<b;i++){
			for(int j=0;j<4;j++){
				for(int k=0;k<2;k++){
					if(!dp[i][j][k])continue;
					if(s[i]){
						for(int l=0;l<4;l++)if(s[i]==(1<<l)){
							if(l+j==3||l==j)continue;
							int tk=k;
							if(j+1==l){
								tk=1;
							}
							dp[i+1][l][tk]=(dp[i+1][l][tk]+dp[i][j][k])%mod;
						}
					}else{
						for(int l=0;l<4;l++){
							if(l+j==3||l==j)continue;
							int tk=k;
							if(j+1==l){
								tk=1;
							}
							dp[i+1][l][tk]=(dp[i+1][l][tk]+dp[i][j][k])%mod;
						}
					}
				}
			}
		}
		for(int i=0;i<4;i++)ret=(ret+dp[b][i][1])%mod;
	}
//	printf("%lld\n",ret);
	dame=false;
	for(int i=0;i<a;i++)if(__builtin_popcount(t[i])>1)dame=true;
	if(!dame){
		for(int i=0;i<4;i++){
			if(t[0]==0||t[0]==(1<<i)){
				dp2[1][i]=1;
			}
		}
		for(int i=1;i<a;i++){
			for(int j=0;j<4;j++){
				if(!dp2[i][j])continue;
				for(int k=0;k<4;k++){
					if(t[i]==0||t[i]==(1<<k)){
						if((j^k)==1||j==k)continue;
						dp2[i+1][k]=(dp2[i+1][k]+dp2[i][j])%mod;
					}
				}
			}
		}
		for(int i=0;i<4;i++)ret=(ret+dp2[a][i])%mod;
	}
	//printf("%lld\n",ret);
	long long ks=1;
	if(c==0)ks=2;
	int key=0;
	
	//if(key==3)ks=0;
	for(int i=0;i<b;i++){
		L[0][i]=-9999999;
		L[1][i]=9999999;
		if(i){
			keyL[i]|=keyL[i-1];
			L[0][i]=max(L[0][i],L[0][i-1]);
			L[1][i]=min(L[1][i],L[1][i-1]);
		}
		for(int j=0;j<2;j++){
			for(int k=0;k<v[j][i].size();k++){
				if(j==0)L[1][i]=min(L[1][i],v[j][i][k]);
				else L[0][i]=max(L[0][i],v[j][i][k]);
			}
		}
		for(int j=0;j<v2[i].size();j++){
			keyL[i]|=1<<((i^(v2[i][j].first)^(v2[i][j].second/2))%2);
		}
	}
	for(int i=b-1;i>=0;i--){
		R[0][i]=-9999999;
		R[1][i]=9999999;
		if(i<b-1){
			keyR[i]|=keyR[i+1];
			R[0][i]=max(R[0][i],R[0][i+1]);
			R[1][i]=min(R[1][i],R[1][i+1]);
		}
		for(int j=0;j<2;j++){
			for(int k=0;k<v[j][i].size();k++){
				if(j==0)R[0][i]=max(R[0][i],v[j][i][k]);
				else R[1][i]=min(R[1][i],v[j][i][k]);
			}
		}
		for(int j=0;j<v2[i].size();j++){
			keyR[i]|=1<<((i^(v2[i][j].first)^(v2[i][j].second/2))%2);
		}
	}
	for(int i=0;i<b-1;i++){
	//	printf("%d: %d %d %d %d %d %d\n",i,keyL[i],keyR[i+1],L[0][i],L[1][i],R[0][i+1],R[1][i+1]);
		if(__builtin_popcount(keyL[i])>1)continue;
		if(__builtin_popcount(keyR[i+1])>1)continue;
		if(keyL[i]&keyR[i+1])continue;
		ret=(ret+ks*min(a,max(0,min(a,min(L[1][i],R[1][i+1]))-max(0,max(L[0][i],R[0][i+1])))))%mod;
	}
	printf("%lld\n",ret);
}