记录编号	249094	评测结果	AAAAAAAAAA
题目名称	2220.[SDOI 2016] 储能表	最终得分	100
用户昵称	铁策	是否通过	通过
代码语言	C++	运行时间	0.332 s
提交时间	2016-04-11 23:08:58	内存使用	2.25 MiB

#include <cstdio>
#include <cmath>
#define lowbit(x) (x & -x)
long long T;
long long n, m, k, p;
inline long long prod(long long x, long long y)
{
	return (x % p) * (y % p) % p;
} 
long long getans(long long n, long long m, long long k)
{
	if (k < 0)
		k = 0;
	if (n == 0 || m == 0)
		return 0;
	if (n < m)
		return getans(m, n, k);
	if (lowbit(n) == n && lowbit(m) == m && n == m)
	{
		if (k >= n)
			return 0;
		long long ls = n - k - 1;
		if (ls & 1)
			ls = prod(ls, (n - k) / 2);
		else
			ls = prod(ls / 2, n - k);
		ls = prod(ls, n);
		return ls;
	}
	long long lsn = (long long)log2(n), lsm = (long long)log2(m);
	if (lsn == lsm)
	{
		long long ls1 = getans(1LL << lsn, 1LL << lsn, k);
		long long ls2 = n - (1LL << lsn);
		long long ls3 = m - (1LL << lsn);
		if (k >= (1LL << (lsn + 1)) - 1)
			return 0;
		if (k <= (1LL << lsn))
		{
			long long ls = (1LL << lsn) - 1;
			if (ls & 1)
				ls = prod(ls, (1LL << lsn) / 2);
			else
				ls = prod(ls / 2, 1LL << lsn);
			ls = prod(ls, (ls3 % p + ls2 % p));				
			ls = (ls + prod(prod((1LL << lsn) - k, (ls3 % p) + (ls2 % p)), 1LL << lsn)) % p;
			ls1 = (ls1 + ls) % p;
			ls1 = (ls1 + getans(n & ((1LL << lsn) - 1), m & ((1LL << lsn) - 1), k)) % p;
			return ls1;
		}
		long long lsk = k - (1LL << lsn);
		long long ls = (1LL << lsn) - lsk - 1;
		if (ls & 1)
			ls = prod(ls, ((1LL << lsn) - lsk) / 2);
		else
			ls = prod(ls / 2, (1LL << lsn) - lsk);
		ls = prod(ls, (ls3 % p + ls2 % p));
		ls1 = (ls1 + ls) % p;
		ls1 = (ls1 + getans(n & (((1LL << lsn)) - 1), m & (((1LL << lsn)) - 1), k)) % p;
		return ls1;
	}
	else
	{
		long long ls = (((1LL << lsn))) - k - 1;
		if (ls < 0)
			ls = 0;
		if (ls & 1)
			ls = prod(ls, ((1LL << lsn) - k) / 2);
		else
			ls = prod(ls / 2, (1LL << lsn) - k);
		ls = prod(ls, m);
		ls = (ls + getans(n & (((1LL << lsn)) - 1), m, k - (1LL << (lsn)))) % p;
		if ((1LL << lsn) - k - 1 >= 0)
			ls = (ls + prod(prod((1LL << lsn) - k, m), n & ((1LL << lsn) - 1))) % p;
		return ls;
	}
}
int main()
{
	freopen("menci_table.in", "r", stdin);
	freopen("menci_table.out", "w", stdout);
	scanf("%lld", &T);
	for (; T > 0; T--)
	{
		scanf("%lld%lld%lld%lld", &n, &m, &k, &p);
		printf("%lld\n", getans(n, m, k));
	}
	return 0;
}