Partial Sums V2

题目连接：

Description

给出一个数组A，经过一次处理，生成一个数组S，数组S中的每个值相当于数组A的累加，比如：A = {1 3 5 6} => S = {1 4 9 15}。如果对生成的数组S再进行一次累加操作，{1 4 9 15} => {1 5 14 29}，现在给出数组A，问进行K次操作后的结果。(输出结果 Mod 10^9 + 7)

Input

第1行，2个数N和K，中间用空格分隔，N表示数组的长度，K表示处理的次数（2 <= n <= 50000, 0 <= k <= 10^9, 0 <= a[i] <= 10^9)

Output

共N行，每行一个数，对应经过K次处理后的结果。输出结果 Mod 10^9 + 7。

Sample Input

4 2

Sample Output

题意：

题解：

考虑每个位置的贡献，所求即$ans[n]=\sum_{i+j=n}^{}C(k-1+i,i)\cdot a[j]$ ，其中 $C(n,i) $表示从 n 个物品里选出 i 个物品的方案数。

上述卷积形式可以利用FFT或NTT加速运算，难点在于答案模 109+7，设其为 P ，这意味这参与卷积的每个元素值为不大于 (P−1) 的非负整数，卷积后的值为不大于 (n+1)⋅(P−1)2=O(nP2) 的值，这个上界可以达到 5⋅1022 。

一种想法是利用3种模意义下的NTT结果进行合并，得到这个可能达到 5⋅1022 的数，再取模，一共需要9次NTT，涉及高精度。

还有一种想法就是降低卷积前的元素值上界，令 M 为满足 P≤M2 的最小正整数，将多项式 f 拆成 f1+f2⋅M 的形式，那么每个元素的值上界是 O(M)=O($\sqrt{p}$) 的，卷积后的值上界是 O(nP) 的，用long double来做FFT差不多可以接受，而卷积可以写为 f∗g=(f1+f2⋅M)∗(g1+g2⋅M)=(f1∗f2)+(f1∗g2+f2∗g1)⋅M+(f2∗g2)⋅M2 ，一共需要7次FFT，不涉及高精度。

很邪，51nod上c++会wa，c++11会过..

以前只在大牛的博客上看到过第一种做法，但没有实用性，第二种方法很强。

昨天刚好看到，拉出来封个版

----------

2016-8-18 更新

看到另一种黑科技优化，大概是fft中用了相位的部分，只用4次fft，膜

代码

1 //#include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
               10 #include 
              
                11 #include 
               
                 12 #include 
                 13 #include 
                 
                   14 #include 
                  
                    15 #include 
                   
                     16 #include 
                    
                      17 using namespace std; 18 long double esp=1e-11; 19 //#pragma comment(linker, "/STACK:1024000000,1024000000") 20 #define fi first 21 #define se second 22 #define all(a) (a).begin(),(a).end() 23 #define cle(a) while(!a.empty())a.pop() 24 #define mem(p,c) memset(p,c,sizeof(p)) 25 #define mp(A, B) make_pair(A, B) 26 #define pb push_back 27 #define lson l , m , rt << 1 28 #define rson m + 1 , r , rt << 1 | 1 29 typedef long long int LL; 30 const long double PI = acos((long double)-1); 31 const LL INF=0x3f3f3f3fll; 32 const int MOD =1000000007ll; 33 const int maxn=140100; 34 struct complex 35 { 36 long double r,i; 37 complex(long double _r = 0.0,long double _i = 0.0){r = _r; i = _i;} 38 complex operator +(const complex &b){ return complex(r+b.r,i+b.i);} 39 complex operator -(const complex &b){ return complex(r-b.r,i-b.i);} 40 complex operator *(const complex &b){ return complex(r*b.r-i*b.i,r*b.i+i*b.r);} 41 }; 42 complex conj(complex a){ return complex(a.r,-a.i);} 43 void change(complex y[],int len) 44 { 45 int i,j,k; 46 for(i = 1, j = len/2;i < len-1; i++) 47 { 48 if(i < j)swap(y[i],y[j]); 49 k = len/2; 50 while( j >= k) 51 { 52 j -= k; 53 k /= 2; 54 } 55 if(j < k) j += k; 56 } 57 } 58 void FFT(complex y[],int len,int on) //len=2^k 59 { 60 change(y,len); 61 for(int h = 2; h <= len; h <<= 1) 62 { 63 complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h)); 64 for(int j = 0;j < len;j+=h) 65 { 66 complex w(1,0); 67 for(int k = j;k < j+h/2;k++) 68 { 69 complex u = y[k]; 70 complex t = w*y[k+h/2]; 71 y[k] = u+t; 72 y[k+h/2] = u-t; 73 w = w*wn; 74 } 75 } 76 } 77 if(on == -1) 78 for(int i = 0;i < len;i++) 79 y[i].r /= len; 80 } 81 int callen(int len1,int len2){ 82 int len=1; 83 while(len < (len1<<1) || len < (len2<<1))len<<=1; 84 return len; 85 } 86 LL fftans[maxn]; 87 complex A[maxn],B[maxn],dft[4][maxn],dt[4]; 88 int td[4]; 89 void fft(LL* y1,int len1,LL* y2,int len2,LL mod){ 90 int len=callen(len1,len2); 91 for(int x=0;x
                     
                      >15); 92 for(int x=len1;x
                      
                       >15); 94 for(int x=len2;x

::iterator iter;133 //for(int x=1;x<=n;x++)134 //for(int y=1;y<=n;y++)135 //scanf("%d",&a);136 //printf("%d\n",ans);137 int n;138 LL k;139 scanf("%d%lld",&n,&k);140 inv[1]=1;141 for(int x=2;x

2016-08-18

转载于:https://www.cnblogs.com/femsub/p/5722066.html

你可能感兴趣的文章