fork(1) download
copy 
  1. /*__ _(_) __ _  ___  ___ _   _  __| | __ _ _   _| |_ ___
  2.  / _` | |/ _` |/ _ \/ __| | | |/ _` |/ _` | | | | __/ _ \
  3. | (_| | | (_| | (_) \__ \ |_| | (_| | (_| | |_| | || (_) |
  4.  \__, |_|\__,_|\___/|___/\__,_|\__,_|\__,_|\__,_|\__\___/
  5.  |___/                                  Accepted Code  */
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8.  
  9. #ifndef M_PI
  10.     #define M_PI 3.141592653589793238462643
  11. #endif
  12.  
  13. const long maxPow=18;
  14. const long absMax=1<<(maxPow-2);
  15. long _cnt[2][2*absMax+1];
  16. #define Cnt(i,x) _cnt[i][x+absMax]
  17.  
  18. template<typename T>
  19. void readNumber(T& x){
  20.     register int c;
  21.     static bool isNega;
  22.     isNega=false;
  23.     while(!((x=getchar())>='-' && x<='9'));
  24.     if(x=='-') isNega=true, x=0; else x-='0';
  25.     while(((c=getchar())>='-' && c<='9')) x=10*x+(c-'0');
  26.     if(isNega) x=-x;
  27. }
  28.  
  29. template<unsigned M, unsigned N, unsigned B, unsigned A>
  30. struct SinCosSeries {
  31.    static double value() {
  32.       return 1-(A*M_PI/B)*(A*M_PI/B)/M/(M+1)
  33.                *SinCosSeries<M+2,N,B,A>::value();
  34.    }
  35. };
  36.  
  37. template<unsigned N, unsigned B, unsigned A>
  38. struct SinCosSeries<N,N,B,A> {
  39.    static double value() { return 1.; }
  40. };
  41.  
  42. template<unsigned B, unsigned A, typename T=double>
  43. struct Sin;
  44.  
  45. template<unsigned B, unsigned A>
  46. struct Sin<B,A,float> {
  47.    static float value() {
  48.       return (A*M_PI/B)*SinCosSeries<2,24,B,A>::value();
  49.    }
  50. };
  51. template<unsigned B, unsigned A>
  52. struct Sin<B,A,double> {
  53.    static double value() {
  54.       return (A*M_PI/B)*SinCosSeries<2,34,B,A>::value();
  55.    }
  56. };
  57.  
  58. ////// template class Cos
  59. // compile-time calculation of cos(A*M_PI/B) function
  60.  
  61. template<unsigned B, unsigned A, typename T=double>
  62. struct Cos;
  63.  
  64. template<unsigned B, unsigned A>
  65. struct Cos<B,A,float> {
  66.    static float value() {
  67.       return SinCosSeries<1,23,B,A>::value();
  68.    }
  69. };
  70. template<unsigned B, unsigned A>
  71. struct Cos<B,A,double> {
  72.    static double value() {
  73.       return SinCosSeries<1,33,B,A>::value();
  74.    }
  75. };
  76.  
  77. template<unsigned N, typename T=double>
  78. class DanielsonLanczos {
  79.    DanielsonLanczos<N/2,T> next;
  80. public:
  81.    void apply(T* data,bool rev) {
  82.       next.apply(data,rev);
  83.       next.apply(data+N,rev);
  84.  
  85.       T wtemp,tempr,tempi,wr,wi,wpr,wpi;
  86.       wtemp = -Sin<N,1,T>::value();
  87.       wpr = -2.0*wtemp*wtemp;
  88.       wpi = -Sin<N,2,T>::value();
  89.       wr = 1.0;
  90.       wi = 0.0;
  91.       for (register unsigned i=0; i<N; i+=2) {
  92.         tempr = data[i+N]*wr - data[i+N+1]*wi;
  93.         tempi = data[i+N]*wi + data[i+N+1]*wr;
  94.         data[i+N] = data[i]-tempr;
  95.         data[i+N+1] = data[i+1]-tempi;
  96.         data[i] += tempr;
  97.         data[i+1] += tempi;
  98.  
  99.         wtemp = wr;
  100.         wr += wr*wpr - wi*wpi;
  101.         wi += wi*wpr + wtemp*wpi;
  102.       }
  103.    }
  104. };
  105.  
  106. template<typename T>
  107. class DanielsonLanczos<1,T> {
  108. public:
  109.    void apply(T* data, bool rev) { }
  110. };
  111.  
  112. template<unsigned P,
  113.          typename T=double>
  114. class GFFT {
  115.    enum { N = 1<<P };
  116.    DanielsonLanczos<N,T> recursion;
  117. public:
  118.     inline void scramble(T* data, unsigned long nn){
  119.         register unsigned long n, j, i, m;
  120.         n = nn<<1;
  121.         j=1;
  122.         for (i=1; i<n; i+=2) {
  123.             if (j>i) {
  124.                 swap(data[j-1], data[i-1]);
  125.                 swap(data[j], data[i]);
  126.             }
  127.             m = nn;
  128.             while (m>=2 && j>m) {
  129.                 j -= m;
  130.                 m >>= 1;
  131.             }
  132.             j += m;
  133.         };
  134.     }
  135.     void fft(T* data, bool rev) {
  136.       scramble(data,N);
  137.       recursion.apply(data, rev);
  138.     }
  139. };
  140.  
  141. template<typename T>
  142. inline void ComplexMulti(T* r, T* p1, T* p2, unsigned long nn){
  143.     unsigned long n=nn<<1;
  144.     for(register unsigned long i=0;i<n;i+=2){
  145.         r[i]=p1[i]*p2[i]-p1[i+1]*p2[i+1],
  146.         r[i+1]=p1[i]*p2[i+1]+p1[i+1]*p2[i];
  147.     }
  148. }
  149.  
  150. enum {pmaxPow=1<<(maxPow)};
  151. GFFT<maxPow,double> fftC;
  152. long N;
  153. double A[1<<(maxPow+1)];
  154. double B[1<<(maxPow+1)];
  155. double AB[1<<(maxPow+1)];
  156. long C[1<<(maxPow)];
  157. int main(){
  158.     readNumber(N);
  159.     register long i,j,x;
  160.     memset(A,0,sizeof(A));
  161.     memset(B,0,sizeof(B));
  162.     for(i=0;i<N;i++) readNumber(x),A[(x+absMax)<<1]+=1.;
  163.     for(i=0;i<N;i++) readNumber(x),B[(x+absMax)<<1]+=1.;
  164.     for(i=0;i<N;i++) readNumber(x),C[(x+absMax)]++;
  165.     fftC.fft(A,false);fftC.fft(B,false);
  166.     ComplexMulti(AB,A,B,pmaxPow);
  167.     fftC.fft(AB,true);
  168.     for(i=0;i<(1<<(maxPow+1));i+=2) AB[i]/=pmaxPow;
  169.     const long zzz=1<<(maxPow+1);
  170.     register long long res=0;
  171.     for(i=0+2*absMax,j=-absMax+absMax;j<=2*absMax;i+=2,j++)
  172.         if(fabs(C[j])>1e-8) res+=1ll*(long)(AB[zzz-i]+.5f)*C[j];
  173.        if(res>13000000000ll) exit(-1);
  174.     printf("%lld\n",res);
  175.     return 0;
  176. }
  177.  
Success #stdin #stdout 0.05s 17840KB
comments (?)
stdin
copy 
3
-1 1 1
-1 2 3
2 3 -2
stdout
copy 
4
https://ideone.com/cpuRUQ
POST2 - A cộng B version 2
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!