现在的位置: 首页 > 综合 > 正文

CC Arithmetic Progressions (FFT + 分块处理)

2017年09月27日 ⁄ 综合 ⁄ 共 4794字 ⁄ 字号 小 中 大 ⁄ 评论关闭
分类： ACM_数学类2013-07-25
21:27 505人阅读 评论(0) 收藏 举报

转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents    by---cxlove 

题目：给出n个数，选出三个数，按下标顺序形成等差数列

http://www.codechef.com/problems/COUNTARI

如果只是形成 等差数列并不难，大概就是先求一次卷积，然后再O(n)枚举，判断2 * a[i]的种数，不过按照下标就不会了。

有种很矬的，大概就是O(n)枚举中间的数，然后 对两边分别卷积，O(n * n * lgn)。

如果能想到枚举中间的数的话，应该可以进一步想到分块处理。

如果分为K块

那么分为几种情况 ：

三个数都是在当前块中，那么可以枚举后两个数，查找第一个数，复杂度O(N/K * N/K)

两个数在当前块中，那么另外一个数可能在前面，也可能在后面，同理还是枚举两个数，查找，复杂度
O(N/K * N/K)

如果只有一个数在当前块中，那么就要对两边的数进行卷积，然后枚举当前块中的数，查询2 × a[i]。复杂度O(N * lg N)

那么总体就是O(k * (N/K * N/K + N * lg N))。

[cpp] view
plaincopy

  1. #include <iostream>  
  2. #include <cstdio>  
  3. #include <cstring>  
  4. #include <cmath>  
  5. #include <algorithm>  
  6. using namespace std;  
  7. //FFT copy from kuangbin  
  8. const double pi = acos (-1.0);  
  9. // Complex  z = a + b * i    
  10. struct Complex {  
  11.     double a, b;  
  12.     Complex(double _a=0.0,double _b=0.0):a(_a),b(_b){}  
  13.     Complex operator + (const Complex &c) const {  
  14.         return Complex(a + c.a , b + c.b);  
  15.     }  
  16.     Complex operator - (const Complex &c) const {  
  17.         return Complex(a - c.a , b - c.b);  
  18.     }  
  19.     Complex operator * (const Complex &c) const {  
  20.         return Complex(a * c.a - b * c.b , a * c.b + b * c.a);  
  21.     }  
  22. };  
  23. //len = 2 ^ k  
  24. void change (Complex y[] , int len) {  
  25.     for (int i = 1 , j = len / 2 ; i < len -1 ; i ++) {  
  26.         if (i < j) swap(y[i] , y[j]);  
  27.         int k = len / 2;  
  28.         while (j >= k) {  
  29.             j -= k;  
  30.             k /= 2;  
  31.         }  
  32.         if(j < k) j += k;  
  33.     }   
  34. }  
  35. // FFT   
  36. // len = 2 ^ k  
  37. // on = 1  DFT    on = -1 IDFT  
  38. void FFT (Complex y[], int len , int on) {  
  39.     change (y , len);  
  40.     for (int h = 2 ; h <= len ; h <<= 1) {  
  41.         Complex wn(cos (-on * 2 * pi / h), sin (-on * 2 * pi / h));  
  42.         for (int j = 0 ; j < len ; j += h) {  
  43.             Complex w(1 , 0);  
  44.             for (int k = j ; k < j + h / 2 ; k ++) {  
  45.                 Complex u = y[k];  
  46.                 Complex t = w * y [k + h / 2];  
  47.                 y[k] = u + t;  
  48.                 y[k + h / 2] = u - t;  
  49.                 w = w * wn;  
  50.             }  
  51.         }  
  52.     }  
  53.     if (on == -1) {  
  54.         for (int i = 0 ; i < len ; i ++) {  
  55.             y[i].a /= len;  
  56.         }  
  57.     }  
  58. }  
  59. const int N = 100005;  
  60. typedef long long LL;  
  61. int n , a[N];  
  62. int block , size;  
  63. LL num[N << 2];  
  64. int min_num = 30000 , max_num = 1;  
  65. int before[N] = {0}, behind[N] = {0} , in[N] = {0};  
  66. Complex x1[N << 2] ,x2[N << 2];  
  67. int main () {  
  68.     #ifndef ONLINE_JUDGE  
  69.         freopen("input.txt" , "r" , stdin);  
  70.     #endif  
  71.     scanf ("%d", &n);  
  72.     for (int i = 0 ; i < n ; ++ i) {  
  73.         scanf ("%d", &a[i]);  
  74.         behind[a[i]] ++;  
  75.         min_num = min (min_num , a[i]);  
  76.         max_num = max (max_num , a[i]);  
  77.     }  
  78.     LL ret = 0;  
  79.     block = min(n , 35);  
  80.     size = (n + block - 1) / block;  
  81.     for (int t = 0 ; t < block ; t ++) {  
  82.         int s = t * size , e = (t + 1) * size;  
  83.         if (e > n) e = n;  
  84.         for (int i = s ; i < e ; i ++) {  
  85.             behind[a[i]] --;  
  86.         }  
  87.         for (int i = s ; i < e ; i ++) {  
  88.             for (int j = i + 1 ; j < e ; j ++) {  
  89.                 int m = 2 * a[i] - a[j];  
  90.                 if(m >= 1 && m <= 30000) {   
  91.                     // both of three in the block  
  92.                     ret += in[m];  
  93.                     // one of the number in the pre block  
  94.                     ret += before[m];  
  95.                 }  
  96.                 m = 2 * a[j] - a[i];  
  97.                 if (m >= 1 && m <= 30000) {  
  98.                     // one of the number in the next block  
  99.                     ret += behind[m];  
  100.                 }  
  101.             }  
  102.             in[a[i]] ++;  
  103.         }  
  104.         // pre block , current block , next block  
  105.         if (t > 0 && t < block - 1) {  
  106.             int l = 1;  
  107.             int len = max_num + 1;  
  108.             while (l < len * 2) l <<= 1;  
  109.             for (int i = 0 ; i < len ; i ++) {  
  110.                 x1[i] = Complex (before[i] , 0);  
  111.             }  
  112.             for (int i = len ; i < l ; i ++) {  
  113.                 x1[i] = Complex (0 , 0);  
  114.             }  
  115.             for (int i = 0 ; i < len ; i ++) {  
  116.                 x2[i] = Complex (behind[i] , 0);  
  117.             }  
  118.             for (int i = len ; i < l ; i ++) {  
  119.                 x2[i] = Complex (0 , 0);  
  120.             }  
  121.             FFT (x1 , l , 1);  
  122.             FFT (x2 , l , 1);  
  123.             for (int i = 0 ; i < l ; i ++) {  
  124.                 x1[i] = x1[i] * x2[i];  
  125.             }  
  126.             FFT (x1 , l , -1);  
  127.             for (int i = 0 ; i < l ; i ++) {  
  128.                 num[i] = (LL)(x1[i].a + 0.5);  
  129.             }  
  130.             for (int i = s ; i < e ; i ++) {  
  131.                 ret += num[a[i] << 1];  
  132.             }  
  133.         }  
  134.         for (int i = s ; i < e ; i ++) {  
  135.             in[a[i]] --;  
  136.             before[a[i]] ++;  
  137.         }  
  138.     }  
  139.     printf("%lld\n", ret);  
  140.     return 0;  
  141. }  
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞