记录编号	399375	评测结果	AAAAAAAAAA
题目名称	[HAOI 2017]方案数	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	3.193 s
提交时间	2017-04-26 13:23:32	内存使用	5.83 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=110,O=1e4+10,p=119<<23|1;
struct pt{ll x,y,z;}P[O];
ll n,m,r;int o,size;
bool OK(ll &s,ll &t){return (s&t)==s;}
bool cmp(const pt &a,const pt &b){
	if (a.x!=b.x) return a.x<b.x;
	if (a.y!=b.y) return a.y<b.y;
	return a.z<b.z;
}
int C[N][N],v[N][N][N];
int inc(int x,int y){x+=y;return x>=p?x-p:x;}
int dec(int x,int y){x-=y;return x<0?x+p:x;}
int mul(int x,int y){return (ll)x*y%p;}
void init(){
	for (int i=0;i<N;i++){
		C[i][0]=1;
		for (int j=1;j<=i;j++) C[i][j]=inc(C[i-1][j-1],C[i-1][j]);
	}
	v[0][0][0]=1;
	for (int i=0;i<=64;i++)
	for (int j=0;j<=64;j++)
	for (int k=0;k<=64;k++)
	for (int l=0;l<=64;l++){
		if (l>i) v[l][j][k]=inc(v[l][j][k],mul(v[i][j][k],C[l][i]));
		if (l>j) v[i][l][k]=inc(v[i][l][k],mul(v[i][j][k],C[l][j]));
		if (l>k) v[i][j][l]=inc(v[i][j][l],mul(v[i][j][k],C[l][k]));
	}
}
int cnt(ll x){
	int ans=0;
	for (;x;x-=x&-x) ans++;
	return ans;
}
int cx[O],cy[O],cz[O];
int DP[2][O],*x=DP[0],*y=DP[1];
int main()
{
	freopen("problema.in","r",stdin);
	freopen("problema.out","w",stdout);
	scanf("%lld%lld%lld",&n,&m,&r);
	scanf("%d",&o);
	for (int i=1;i<=o;i++){
		ll x,y,z;
		scanf("%lld%lld%lld",&x,&y,&z);
		if (OK(x,n)&&OK(y,m)&&OK(z,r)) P[++size]=(pt){x,y,z};
	}
	sort(P+1,P+size+1,cmp);
	for (int i=1;i<=size;i++){
		cx[i]=cnt(P[i].x);
		cy[i]=cnt(P[i].y);
		cz[i]=cnt(P[i].z);
	}
	init();
	cx[size+1]=cnt(n);
	cy[size+1]=cnt(m);
	cz[size+1]=cnt(r);
	for (int la=0;la<=size;la++)
		x[la]=v[cx[size+1]-cx[la]][cy[size+1]-cy[la]][cz[size+1]-cz[la]];
	for (int p=size;p;p--,swap(x,y))
	for (int la=0;la<p;la++){
		y[la]=x[la];
		if (OK(P[la].x,P[p].x)&&OK(P[la].y,P[p].y)&&OK(P[la].z,P[p].z))
			y[la]=dec(y[la],mul(v[cx[p]-cx[la]][cy[p]-cy[la]][cz[p]-cz[la]],x[p]));
	}
	printf("%d\n",x[0]);
	return 0;
}