记录编号	156194	评测结果	AAAAA
题目名称	[CF 249E]无尽的矩阵	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	2.415 s
提交时间	2015-04-03 10:55:04	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define sqr(x) ((x)*(x))
typedef long long LL;
LL MOD;
inline LL realmod(LL x){
	x%=MOD;
	if(x<0) x+=MOD;
	return x;
}
inline LL quickmul(LL x,LL y){
	x=realmod(x),y=realmod(y);
	return ((x*y-(LL)(((long double)x*y+0.5)/MOD)*MOD)%MOD+MOD)%MOD;
}
inline LL series_1(LL a,LL b,LL n){//一阶级数
	//首项为a,公差为b,共n项
	a=realmod(a),b=realmod(b);
	LL ans=quickmul(a,n);
	static LL c[2];
	c[0]=n-1,c[1]=n;
	for(int i=0;i<2;i++){if(c[i]%2==0){c[i]/=2;break;}}
	ans+=quickmul(b,quickmul(c[0],c[1]));
	return realmod(ans);
}
inline LL series_2(LL a2,LL a1,LL b,LL n){//二阶级数
	//首项为a2,第一次加a1,然后每次多加b,共n项
	a2=realmod(a2),a1=realmod(a1),b=realmod(b);
	LL ans=series_1(a2,a1,n);
	static LL c[3];
	c[0]=n-2,c[1]=n-1,c[2]=n;
	for(int i=0;i<3;i++){if(c[i]%2==0){c[i]/=2;break;}}
	for(int i=0;i<3;i++){if(c[i]%3==0){c[i]/=3;break;}}
	ans+=quickmul(b,quickmul(c[0],quickmul(c[1],c[2])));
	ans=realmod(ans);
	return realmod(ans);
}
inline LL calc(LL x,LL y){
	if(x<1||y<1) return 0;
	LL ans;
	ans=series_1(1,1,sqr(min(x,y)));
	if(x>y){
		LL a2=series_1((y+1)*(y+1),-1,y);
		LL a1=realmod((2*y+3)*y);
		LL b=realmod(2*y);
		ans+=series_2(a2,a1,b,x-y);
	}
	else if(y>x){
		LL a2=series_1(x*x+1,1,x);
		LL a1=realmod((2*x+1)*x);
		LL b=realmod(2*x);
		ans+=series_2(a2,a1,b,y-x);
	}
	return ans;
}
inline LL calc(LL x1,LL y1,LL x2,LL y2){
	return realmod(calc(x2,y2)-calc(x2,y1-1)-calc(x1-1,y2)+calc(x1-1,y1-1));
}
LL mod1=1e10,mod2=1e10+9;
inline void work(void){
	int x1,y1,x2,y2;
	scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
	MOD=mod1;
	LL res1=calc(x1,y1,x2,y2);
	MOD=mod2;
	LL res2=calc(x1,y1,x2,y2);
	if(res1!=res2){
		printf("...");
		printf("%.10lld\n",res1);
	}
	else printf("%lld\n",res1);
}
int main(){
	freopen("endlessmatrix.in","r",stdin);
	freopen("endlessmatrix.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T--) work();
	return 0;
}