记录编号	267543	评测结果	AAAAAAAAAA
题目名称	[SDOI 2016] 储能表	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	0.870 s
提交时间	2016-06-11 15:48:44	内存使用	0.25 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;

LL n,m,k,mod,len;
LL Max(LL a,LL b){
	return a>b?a:b;
}

LL Mul(LL a,LL b){
	LL ret=0;
	a%=mod;b%=mod;
	while(a){
		if(a&1)ret=(ret+b)%mod;
		a>>=1;b<<=1;
	}
	return ret;
}

LL Calc1(LL h,LL tot){
	LL t=h+tot-1,ret=0;
	h=Max(1,h-k);t-=k;
	if(h>t)return 0;
	if((h+t)&1) ret=Mul(Mul((h+t),(t-h+1)/2),tot);
	else ret=Mul(Mul((t-h+1),((h+t)/2)),tot);
	return ret;
}

LL Calc2(LL h,LL t,LL lb){
	LL ret=0;
	h=Max(1ll,h-k);t-=k;
	if(h>t)return 0;
	if((h+t)&1) ret=Mul(Mul((h+t),(t-h+1)/2),lb);
	else ret=Mul(Mul((t-h+1),((h+t)/2)),lb);
	return ret;
}

LL Solve(LL qa,LL qb,LL x1,LL y1,LL x2,LL y2,LL l){
	if(x1<y1){swap(qa,qb);swap(x1,y1);swap(x2,y2);}	
	if(qa>=x2&&qb>=y2){return Calc1(x1^y1,l);}
	else if(qa>=x2){return Calc2(x1^y1,(x1^y1)+l-1,qb-y1);}
	else if(qb>=y2){return Calc2(x1^y1,(x1^y1)+l-1,qa-x1);}
	LL mx=(x1+x2)>>1,my=(y1+y2)>>1,ret=0;
	if(x1<qa&&y1<qb)ret=(ret+Solve(qa,qb,x1,y1,mx,my,l>>1))%mod;
	if(mx<qa&&y1<qb)ret=(ret+Solve(qa,qb,mx,y1,x2,my,l>>1))%mod;
	if(x1<qa&&my<qb)ret=(ret+Solve(qa,qb,x1,my,mx,y2,l>>1))%mod;
	if(mx<qa&&my<qb)ret=(ret+Solve(qa,qb,mx,my,x2,y2,l>>1))%mod;	
	return ret;
}
int main(){
	freopen("menci_table.in","r",stdin);
	freopen("menci_table.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%lld%lld%lld%lld",&n,&m,&k,&mod);
		if(n<m)swap(n,m);len=1;
		while(len<n)len<<=1;
		printf("%lld\n",Solve(n,m,0,0,len,len,len));
	}
	return 0;	
}