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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

Codechef Arithmetic Progressions COUNTARI  

2013-04-03 14:17:43|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
不要以为我在做CC。。只是为了廖哥要我们轮流讲课。。。于是我想讲讲快速傅里叶变化,结果发现这方面的题目少得可怜。。于是网上搜也没搜到几题,这题已经是相当了不起的不是特别特别裸的题了。
题意是这样的。。求一个数列中长度为3的子序列中等差数列的个数。每个数的大小小于30000
这题的感想就是。。。CC的机子跑得飞快飞快的,竟然这样都能过的,太奇葩了
做法。。分块流,大概是30块吧,每块外面暴力FFT,内部暴枚。算法不是很难。脑残了一会,于是纠结了好久。。我是不是太傻了呢?
代码:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<fstream>
#include<map>
#include<ctime>
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<functional>
#include<complex>
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
#define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
using namespace std;

typedef long long LL;
typedef double ld;
typedef complex<ld> Complex;

const int MAX=100000+10;
const int LEN=16;
const int NUM=1<<16;

int n;
int a[MAX],Size;
int num[NUM],inside[NUM];
int ll[NUM],in_ll[NUM];
LL ans;

Complex w[NUM],p1[NUM],p2[NUM],temp[NUM];

void fft(Complex* p,int deep,int flag)
{
if(deep==LEN)return;
int step=(1<<deep);
fft(p,deep+1,flag);
fft(p+step,deep+1,flag);
int num=1<<(LEN-deep);
int i,ss=0,half=num/2;
Complex a,b;
REP2(i,0,half)
{
a=p[ss];
b=p[ss+step];
if(!flag)b*=w[i<<deep];
else b/=w[i<<deep];
temp[i]=a+b;
temp[i+half]=a-b;
ss+=2*step;
}
REP2(i,0,num)
p[i*step]=temp[i];
return;
}

void count(int u)
{
int i,j;
int l=u*Size,r=min( (u+1)*Size,n );
memset(inside,0,sizeof inside);
memset(in_ll,0,sizeof in_ll);
REP2(i,l,r)
++inside[a[i]];
REP2(i,0,NUM)
{
p1[i]=Complex( ll[i] , 0 );
p2[i]=Complex( num[i]-ll[i]-inside[i] , 0 );
}
fft(p1,0,0);
fft(p2,0,0);
REP2(i,0,NUM)
p1[i]*=p2[i];
fft(p1,0,1);
REP2(i,l,r)
{
++in_ll[a[i]];
int aim=2*a[i];
ans+=round( p1[aim].real()/NUM );
REP2(j,l,r)
if(j<i && aim-a[j]>=0)
{
int to=aim-a[j];
if(to>=0)ans+=num[to]-ll[to]-in_ll[to];
}
else if(j>i && aim-a[j]>=0)
{
int to=aim-a[j];
if(to>=0)ans+=ll[to];
}
}
REP2(i,l,r)
++ll[a[i]];
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
int i;
scanf("%d",&n);
REP2(i,0,n)
{
scanf("%d",&a[i]);
--a[i];
++num[a[i]];
}
/*
n*n/K == K*30000*16
*/
REP2(i,0,NUM)
w[i]=Complex(cos(2*M_PI*i/NUM),sin(2*M_PI*i/NUM));
Size=ceil( (ld)n/30 );
int u=0;
while(u*Size<n)
{
count(u);
u++;
}
cout<<ans<<endl;
return 0;
}




  评论这张
 
阅读(653)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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