记录编号	399369	评测结果	AAAAAAAAAA
题目名称	2672.[HAOI 2017]方案数	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.108 s
提交时间	2017-04-26 12:53:24	内存使用	9.73 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;
}
//dp[i][j]表示取i位,用了j次的方案数 
int dp[N][N],C[1010][1010];
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<1010;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]);
	}
	dp[0][0]=1;
	for (int i=0;i<=64;i++)
	for (int j=0;j<=64;j++)
	for (int k=1;i+k<=64;k++)
		dp[i+k][j+1]=inc(dp[i+k][j+1],mul(dp[i][j],C[i+k][i]));
}
int cnt(ll x){
	int ans=0;
	for (;x;x-=x&-x) ans++;
	return ans;
}
int v[N][N][N],cx[O],cy[O],cz[O];
int val(int a,int b,int c){
	//int a=cnt(x),b=cnt(y),c=cnt(z);
	if (a<b) swap(a,b);
	if (a<c) swap(a,c);
	if (b<c) swap(b,c); 
	if (v[a][b][c]) return v[a][b][c];
	int ans=0;
	for (int i=0;i<=a;i++)
	for (int j=0;j<=b;j++)
	for (int k=0;k<=c;k++)
		ans=inc(ans,mul(mul(dp[a][i],mul(dp[b][j],dp[c][k])),mul(C[i+j+k][k],C[i+j][j])));
	return v[a][b][c]=ans;
}
int DP[2][O],*x=DP[0],*y=DP[1];
int work(int p,int la){
	//printf("%d %d\n",p,la);
	if (p>size) return val(cnt(n)-cx[la],cnt(m)-cy[la],cnt(r)-cz[la]);
	int ans=work(p+1,la);
	if (OK(P[la].x,P[p].x)&&OK(P[la].y,P[p].y)&&OK(P[la].z,P[p].z))
		ans=dec(ans,mul(work(p+1,p),val(cx[p]-cx[la],cy[p]-cy[la],cz[p]-cz[la])));
	return ans;
}
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();
	//printf("%d\n",work(1,0));
	cx[size+1]=cnt(n);
	cy[size+1]=cnt(m);
	cz[size+1]=cnt(r);
	for (int la=0;la<=size;la++)
		x[la]=val(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(val(cx[p]-cx[la],cy[p]-cy[la],cz[p]-cz[la]),x[p]));
	}
	printf("%d\n",x[0]);
	return 0;
}