主题

主题

 
   

Arithmetic Progressions

原题:http://www.lydsy.com/JudgeOnline/problem.php?id=3509/https://www.codechef.com/problems/COUNTARI

All submissions for this problem are available.

Given N integers A1, A2, …. AN, Dexter wants to know how many ways he can choose three numbers such that they are three consecutive terms of an arithmetic progression.

Meaning that, how many triplets (i, j, k) are there such that 1 ≤ i < j < k ≤ N and Aj - Ai = Ak - Aj.

So the triplets (2, 5, 8), (10, 8, 6), (3, 3, 3) are valid as they are three consecutive terms of an arithmetic

progression. But the triplets (2, 5, 7), (10, 6, 8) are not.

Input

First line of the input contains an integer N (3 ≤ N ≤ 100000). Then the following line contains N space separated integers A1, A2, …, AN and they have values between 1 and 30000 (inclusive).

Output

Output the number of ways to choose a triplet such that they are three consecutive terms of an arithmetic progression.

Example

Input:

10

3 5 3 6 3 4 10 4 5 2

Output:

9

Explanation

The followings are all 9 ways to choose a triplet

1 : (i, j, k) = (1, 3, 5), (Ai, Aj, Ak) = (3, 3, 3)

2 : (i, j, k) = (1, 6, 9), (Ai, Aj, Ak) = (3, 4, 5)

3 : (i, j, k) = (1, 8, 9), (Ai, Aj, Ak) = (3, 4, 5)

4 : (i, j, k) = (3, 6, 9), (Ai, Aj, Ak) = (3, 4, 5)

5 : (i, j, k) = (3, 8, 9), (Ai, Aj, Ak) = (3, 4, 5)

6 : (i, j, k) = (4, 6, 10), (Ai, Aj, Ak) = (6, 4, 2)

7 : (i, j, k) = (4, 8, 10), (Ai, Aj, Ak) = (6, 4, 2)

8 : (i, j, k) = (5, 6, 9), (Ai, Aj, Ak) = (3, 4, 5)

9 : (i, j, k) = (5, 8, 9), (Ai, Aj, Ak) = (3, 4, 5)


题目大意:

找有多少个三元组(Ai,Aj,Ak),满足2Aj=Ai+Ak。


个人解法:

自己居然搞出来了!

BZOJ和vjudge过了,codechef又TLE是smg……反正搞不懂codechef那些啥啥啥的编译器……权当过了好了。

如果可以的话,我们可以枚举每一个数字当做中位数,然后跑一趟FFT。然而时间复杂度爆炸。

但是拿FFT的这个思想一直延伸在脑海。想分块+FFT预处理然而均以失败告终。

后来想到只需要求三元组。

猛然发现分块以后,发现FFT的次数可以变少!

  1. 三个点在块里面的,枚举块,从左到右枚举中间点,维护当前块在中间点之前的桶,枚举右边点,在桶里面查找第三个点。

    时间复杂度为O(Num*Threshold*Threshold)=O(n*Threshold)。

  2. 两个点在块里面的,顺序枚举一遍,找到两个块在中间,一个点在左边的。维护当前块前面的桶,然后同样枚举两个点即可。

    还要逆序枚举一遍,做一样的事情,这次求的是两个点在中间,一个点在右边的。

    这里复杂度是O(Num*Threshold*Threshold)=O(n*Threshold)。

  3. 三个点在不同块里面的,就先删去这个块的点,然后FFT一趟,枚举中间的点然后找和为x的即可。

    这一部分的时间复杂度为O(Num*maxn*log(maxn))。

然后理论分析Threshold的大小:

总的时间复杂度为O(n*Threshold+Num*maxn*log(maxn))。最小化该式子只需令Threshold=maxn*log(maxn)/Threshold,即Threshold=sqrt(maxn*log(maxn))。

理论上是这样的。然而FFT常数巨大。我们把常数当做15好了。那么事实上我们的Threshold=4*sqrt(maxn*log(maxn))。

看到网上的神犇直接调整成常数1800或者3000的……

反正还是过了(虽然很慢)


代码如下:

https://code.csdn.net/snippets/2283051

 
 
评论