这题根本配不上紫题难度，除了细节巨难调以外，思维难度几乎为零。
考虑计算(calc(x,y)=(1,1) ightarrow(x,y))的值，答案即为(calc(x1-1,y1-1)+calc(x2,y2)-calc(x1-1,y2)-calc(x2,y1-1))
-
(x=yquad calc(x,y)=frac12(1+x^2)x^2)
-
(x>yquad calc(x,y)=frac12(1+y^2)y^2+sumlimits_{i=y+1}^x sumlimits_{j=i^2-y+1}^{i^2}j=frac12(1+y^2)y^2+frac12ysumlimits_{i=y+1}^x(2i^2-y+1))
-
(x<yquad calc(x,y)=frac12(1+x^2)x^2+sumlimits_{i=x+1}^y sumlimits_{j=(i-1)^2+1}^{(i-1)^2+x}j=frac12(1+x^2)x^2+frac12xsumlimits_{i=x+1}^y(2i^2-4i+3+x))
如果这题是模(998244353)，(1e9+7)之类的数，那么恭喜做完了。
但这题的模数是(1e10)，不但是合数，乘起来还会爆(long long)，这使我们不得不考虑一些细节。
-
判断是否结果小于(1e10)：再模一个(1e10+9)，比对结果。
-
防止乘法爆(long long)：使用类似快速幂的快速乘法。
-
计算过程中有出现取过模的数除以(2)，导致答案有(5e9)的误差：把模数改为(2e10)
这时发现因为过多的取模，我们完美地(TLE)了，下面有一些卡常(tricks)。
-
因为(1e10)对于(long long)来说很小，所以最后取一次模就好了。
-
快速乘法中建议取一个值，大于这个值再取模。
这样就可以愉快地(AC)本题了，时间复杂度(Theta(nlog n))
代码如下，以供参考：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod1=2e10;
const int mod2=1e10+9;
const int mod3=1e10;
const int val=1e16;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int mod,T;
inline int mul(int x,int y){
int res=0;
while(y){
if(y&1)res+=x;
x<<=1;
if(x>=val)x%=mod;
y>>=1;
}
return res%mod;
}
inline int calc(int x,int y){
if(!x||!y)return 0;
int res=0;
if(x==y){
int t=mul(x,x);
if(t&1)res=mul(t,(t+1)>>1);
else res=mul(t>>1,t+1);
return res;
}else if(x<y){
int t=mul(x,x);
if(t&1)res=mul(t,(t+1)>>1);
else res=mul(t>>1,t+1);
t=mul(x+3,y-x);
t-=mul(x+y+1,(y-x)<<1);
if(y%3==0)t+=mul(y/3,mul(y+1,y<<1|1));
else if(y%3==1)t+=mul(y,mul(y+1,(y<<1|1)/3));
else t+=mul(y,mul((y+1)/3,y<<1|1));
if(x%3==0)t-=mul(x/3,mul(x+1,x<<1|1));
else if(x%3==1)t-=mul(x,mul(x+1,(x<<1|1)/3));
else t-=mul(x,mul((x+1)/3,x<<1|1));
t=t%mod+mod;
if(!(t&1))res=(res+mul(x,t>>1))%mod;
else if(mod&1)res=(res+mul(x,(t+mod)>>1))%mod;
else res=(res+mul(x>>1,t))%mod;
return res;
}else{
swap(x,y);
int t=mul(x,x);
if(t&1)res=mul(t,(t+1)>>1);
else res=mul(t>>1,t+1);
t=mod-mul(y-x,x-1);
if(y%3==0)t+=mul(y/3,mul(y+1,y<<1|1));
else if(y%3==1)t+=mul(y,mul(y+1,(y<<1|1)/3));
else t+=mul(y,mul((y+1)/3,y<<1|1));
if(x%3==0)t-=mul(x/3,mul(x+1,x<<1|1));
else if(x%3==1)t-=mul(x,mul(x+1,(x<<1|1)/3));
else t-=mul(x,mul((x+1)/3,x<<1|1));
t=t%mod+mod;
if(!(t&1))res=(res+mul(x,t>>1))%mod;
else if(mod&1)res=(res+mul(x,(t+mod)>>1))%mod;
else res=(res+mul(x>>1,t))%mod;
return res;
}
}
inline int solve(int x1,int y1,int x2,int y2){
return ((calc(x1-1,y1-1)+calc(x2,y2)-calc(x1-1,y2)-calc(x2,y1-1))%mod+mod)%mod;
}
signed main(){
T=read();
int x1,x2,y1,y2;
while(T--){
x1=read(),y1=read();
x2=read(),y2=read();
mod=mod1;int res1=solve(x1,y1,x2,y2)%mod3;
mod=mod2;int res2=solve(x1,y1,x2,y2);
if(res1^res2)printf("...%.10lld
",res1);
else printf("%lld
",res1);
}
return 0;
}
然而为什么人家都是(8)秒(9)秒，我一个人(48)秒（大雾