注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

那一日,泪水打湿雪花冰冷的心

曾经的滋味,回忆在一次次的离合中,回眸时,那一刻,如涟漪般在一刹那融化

 
 
 

日志

 
 

SPOJ 6408 KKKCT2  

2010-08-10 21:33:27|  分类: spoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
给定x,y计算点在矩形(0,0)~(x,y)内的等腰直角三角形的个数
所有的等腰之间三角形都要这样的形式:(a,b),(a+c,b+d),(a+c-d,b+c+d)令(a,b)分别是零,枚举c,d可以利用乘法原理在O(xy)时间内作出,但此题数据极大,需要枚举x和y分别计数这样O(x+y)时间得出
#include<cstdio>
#include<cstring>
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define i64 long long
const i64 m=2009;
int x,y,t,k1,k2;
i64 ans;
inline i64 aa(i64 a,i64 b,i64 c){//sigma i=0..c (a+i)(b-i)
i64 tmp=(c+1)*c*(c-1)/6;
return (tmp+b*(a+a+c)*(c+1)/2+a*(c+1)*c/2)%m;
}
inline i64 bb(i64 a,i64 b,i64 c){//sigma i=0..c (a-i)(b-i)
return (c*(c+1)*(2*c+1)/6+a*b*(c+1)-(c+1)*c/2*(a+b))%m;
}
void solve(int x,int y){
for(int i=1;i<=x&&i<=y;++i){
if(2*i<=y){
ans=(ans+(i64)(y-i+1+y-i-i+1)*(1+i)/2%m*(x-i+1))%m;
int k=min(y-i+1,x);
ans=(ans+bb(x+1,y-i+1,k)-bb(x+1,y-i+1,i))%m;
}else ans=(ans+(i64)(y-i+1)*(y-i+1+1)/2%m*(x-i+1))%m;
}
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d",&x,&y);
ans=0;
solve(x,y);
solve(y,x);
printf("%lld\n",(ans*2)%m);
}
return 0;
}
  评论这张
 
阅读(272)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018