C++14(g++5.4) 解法, 执行用时: 279ms, 内存消耗: 484K, 提交时间: 2019-10-22 20:32:59

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
ll n,m,k;int P;
const int N=65;
ll dp[N][2][2][2][2];
int fa[N],fb[N],fc[N],l;
 
int C;
 
inline void ADD(ll&x,ll y){(x+=y)%=P;}
 
int makedp(ll n,ll m,ll k,int P){
	memset(fa,0,sizeof(fa));memset(fb,0,sizeof(fb));
	memset(fc,0,sizeof(fc));memset(dp,0,sizeof(dp));
	int i,j,t,a,b,p;n--,m--; dp[0][1][1][1][0]=1;
	for(i=1,j=0;n;n>>=1,i++)fa[i]=n%2;l=max(l,i-1);
	for(i=1,j=0;m;m>>=1,i++)fb[i]=m%2;l=max(l,i-1);
	for(i=1,j=0;k;k>>=1,i++)fc[i]=k%2;l=max(l,i-1);
	for(i=1;2*i<=l;i++){
		swap(fa[i],fa[l-i+1]);
		swap(fb[i],fb[l-i+1]);
		swap(fc[i],fc[l-i+1]);
	}
	for(i=1;i<=l;i++){
		for(j=0;j<=1;j++){
			for(a=0;a<=1;a++){
				for(b=0;b<=1;b++){
					if(dp[i-1][j][a][b][0]==0) continue;
					for(t=0;t<=1;t++)for(p=0;p<=1;p++){
						if((t^p)>fc[i]&&b||t>fa[i]&&j||p>fb[i]&&a) continue;
						ADD(dp[i][j&&t==fa[i]][a&&p==fb[i]][b&&(t^p)==fc[i]][0],dp[i-1][j][a][b][0]);
						ADD(dp[i][j&&t==fa[i]][a&&p==fb[i]][b&&(t^p)==fc[i]][1],dp[i-1][j][a][b][1]*2+(t^p)*dp[i-1][j][a][b][0]);
					}
				}
			}
		}
	}
	return l;
}
 
void work(){
	scanf("%lld%lld%lld%d",&n,&m,&k,&P);
	ll ans=0,sum=0;int i,j,l,t;l=makedp(n,m,max(n,m)<<1,P);
	for(i=0;i<=1;i++)for(j=0;j<=1;j++)
		ans=(ans+dp[l][i][j][0][1])%P;
	l=makedp(n,m,k,P);ans=((ans-n%P*(m%P)%P*(k%P))%P+P)%P;
	for(i=0;i<=1;i++)for(j=0;j<=1;j++)for(t=0;t<=1;t++)
		ans=((ans+k%P*(dp[l][i][j][t][0]%P)%P-dp[l][i][j][t][1])%P+P)%P;
	printf("%lld\n",ans);
}
 
int main(){
	int T;cin>>T;
	while(T--)work();
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 72ms, 内存消耗: 492K, 提交时间: 2020-05-14 18:49:10

#include <iostream>
#include <iomanip>
using namespace std;
typedef long long ll;
ll s[80]={1},k,MOD=998244353,MXP;
ll nx2(ll c)
{
	ll i;
	for (i=0;s[i]!=0;i++)
		if (s[i]>c) return i-1;
	return MXP;
}
ll q(ll s,ll n)
{
	if (n>=s-1) return 0;
	if (n<=0)
		if (s%2==0)
			 return ((-n)%MOD*(s%MOD)%MOD+(s/2)%MOD*((s-1)%MOD))%MOD;
		else 
			return ((-n)%MOD*(s%MOD)%MOD+((s-1)/2)%MOD*(s%MOD))%MOD;
	if ((s-n)%2==0)
		 return ((s-n)/2)%MOD*((s-n-1)%MOD)%MOD;
	else return ((s-n-1)/2)%MOD*((s-n)%MOD)%MOD;
}
ll cc(ll n,ll m,ll k)
{
	ll ans;
//	cout<<n<<' '<<m<<' '<<k<<' ';
	if (n==0||m==0) return 0;
	if (n>m)
	{
		ll p=n;
		n=m;
		m=p;
	}
	ll nx=nx2(m);
//	cout<<s[nx];
	if (s[nx]>n){
		ans=q(s[nx],k)*(n%MOD)%MOD;
		ans+=cc(n,m-s[nx],k-s[nx]);
	}
	else
	{
		ans=((q(s[nx+1],k)-q(s[nx],k)+MOD)%MOD)*((n-s[nx]+m-s[nx])%MOD)%MOD;
		ans+=(q(s[nx],k)%MOD)*(s[nx]%MOD)%MOD;
		ans%=MOD;
		ans+=cc(m-s[nx],n-s[nx],k);
	}
	return ans%MOD;
}
int main()
{
	ll x,y;
	ll n,m,T;
	cin>>T;
	for (ll i=1;s[i-1]*2<=2e18;i++){
		s[i]=s[i-1]*2;
		MXP++;
	}
	while (T--){
	cin>>n>>m>>k>>MOD;
	cout<<cc(n,m,k)<<endl;
	}
}