coreBugZJ

此 blog 已弃。

Hwh’s Problem, FZU 2011年3月月赛之 H, FZU 2017

Problem 2017 Hwh’s Problem

Accept: 11    Submit: 20
Time Limit: 5000 mSec    Memory Limit : 32768 KB

Problem Description

Polynomial is an expression of more than two algebraic terms, esp. the sum of several terms that contain different powers of the same variable(s).

For example, G( p ) = 7 + 6g^1 + 2g^2 + 0g^3 + 113g^4 is an expression.

Hwh is one “SB” ( short for “ShenBen” ) and he always love math!In this problem, you are expected to calculate the coefficients of the polynomial S(g) = G(p)^m, here m is an integer larger than zero.

For example, G(p) = 3 + 2g^1 , and m = 2, then S(g) = 4g^2 + 12g + 9, so the coefficients of S(g) are {4, 12, 9}; G(p) = 3 + 2g^1 , and m = 3, then S(g) = 8g^3 + 36g^2 + 54g + 27, so the coefficients of S(g) are { 8, 36, 54, 27 }.

The coefficients may be so large, so hwh wants to know the coefficients (mod 211812353).

Input

In the first line one integer T indicates the number of test cases. (T <= 1000)

For every case, two integers n and m in a single line, indicate the number of element of the G(p) and the value of m. (2 <= n <= 10^5, 1 <= m <= 50000, n * m <= 10^5)

Then one line has n integers Ki, indicates the i-th coefficient of G(p). (0 <= Ki <= 10^9)

Output

For each test case, output (n – 1)*m + 1 lines, the i-th (i >= 0) line output “[i] = ci”, where ci is the coefficient of g^i in S(g)

Output one blank line after each test case.

Sample Input

2
2 2
3 2
2 3
3 2

Sample Output

[0] = 9
[1] = 12
[2] = 4

[0] = 27
[1] = 54
[2] = 36
[3] = 8

Source

FOJ有奖月赛-2011年03月


全整数 FFT 加速整系数多项式乘法,不能仅仅套模板,需要对 FFT 有一点点理解。。。

1953ms 1796KB

  1 #include <iostream>
  2 #include <cstdio>
  3 
  4 using namespace std;
  5 
  6 template< int L, class T = intclass LT = long long >
  7 class  FFT
  8 {
  9 public : 
 10         FFT() {
 11                 p = -1;
 12         }
 13         void fft( T e[], int &m, int minL ) {
 14                 in( e, m, minL );
 15                 m = n;
 16                 fft();
 17                 out( e );
 18         }
 19         void ifft( T e[], int &m, int minL ) {
 20                 in( e, m, minL );
 21                 m = n;
 22                 ifft();
 23                 out( e );
 24         }
 25         T getP() {
 26                 return p;
 27         }
 28 
 29 public : 
 30         static int isPrime( T x ) {
 31                 T i;
 32                 if ( x < 2 ) {
 33                         return 0;
 34                 }
 35                 /* overflow !! */
 36                 for ( i = 2; (LT)i*<= x; ++i ) {
 37                         if ( x % i == 0 ) {
 38                                 return 0;
 39                         }
 40                 }
 41                 return 1;
 42         }
 43         static T powMod( T a, T b, T c ) {
 44                 T ans = 1;
 45                 a %= c;
 46                 while ( b > 0 ) {
 47                         if ( b & 1 ) {
 48                                 ans = ( (LT)ans * a ) % c;
 49                         }
 50                         a = ( (LT)a * a ) % c;
 51                         b >>= 1;
 52                 }
 53                 return ans;
 54         }
 55 
 56 private : 
 57         /* p is a prime number */
 58         int isG( T g, T p ) {
 59                 T p0 = p - 1, i;
 60                 for ( i = 1; (LT)i*<= p0; ++i ) {
 61                         if ( p0 % i == 0 ) {
 62                                 if ( (powMod(g,i,p)==1&& (i<p0) ) {
 63                                         return 0;
 64                                 }
 65                                 if ( (powMod(g,p0/i,p)==1&& (p0/i<p0) ) {
 66                                         return 0;
 67                                 }
 68                         }
 69                 }
 70                 return 1;
 71         }
 72         int rev_bit( int i ) {
 73                 int j = 0, k;
 74                 for ( k = 0; k < bit; ++k ) {
 75                         j = ( (j<<1)|(i&1) );
 76                         i >>= 1;
 77                 }
 78                 return j;
 79         }
 80         void reverse() {
 81                 int i, j;
 82                 T t;
 83                 for ( i = 0; i < n; ++i ) {
 84                         j = rev_bit( i );
 85                         if ( i < j ) {
 86                                 t = a[ i ];
 87                                 a[ i ] = a[ j ];
 88                                 a[ j ] = t;
 89                         }
 90                 }
 91         }
 92         void in( T e[], int m, int minL ) {
 93                 int i;
 94                 bit = 0;
 95                 while ( (1<<(++bit)) < minL )
 96                         ;
 97                 n = (1<<bit);
 98                 for ( i = 0; i < m; ++i ) {
 99                         a[ i ] = e[ i ];
100                 }
101                 for ( i = m; i < n; ++i ) {
102                         a[ i ] = 0;
103                 }
104                 if ( p < 0 ) {
105                         init( 21211812353 );
106                 }
107         }
108         // lim2 >= bit
109         void init( int lim2, T minP ) {
110                 T k = 2, ig = 2;
111                 int i;
112                 do {
113                         ++k;
114                         p = ( (k<<lim2) | 1 );
115                 } while ( (p<minP) || (!isPrime(p)) );
116                 while ( !isG(ig,p) ) {
117                         ++ig;
118                 }
119                 for ( i = 0; i < bit; ++i ) {
120                         g[ i ] = powMod( ig, (k<<(lim2-bit+i)), p );
121                 }
122         }
123         void fft() {
124                 T w, wm, u, t;
125                 int s, m, m2, j, k;
126                 reverse();
127                 for ( s = bit-1; s >= 0--s ) {
128                         m2 = (1<<(bit-s));
129                         m = (m2>>1);
130                         wm = g[ s ];
131                         for ( k = 0; k < n; k += m2 ) {
132                                 w = 1;
133                                 for ( j = 0; j < m; ++j ) {
134                                         t = ((LT)(w)) * a[k+j+m] % p;
135                                         u = a[ k + j ];
136                                         a[ k + j ] = ( u + t ) % p;
137                                         a[ k + j + m ] = ( u + p - t ) % p;
138                                         w = ( ((LT)w) * wm ) % p;
139                                 }
140                         }
141                 }
142         }
143         void ifft() {
144                 T w, wm, u, t, inv;
145                 int s, m, m2, j, k;
146                 reverse();
147                 for ( s = bit-1; s >= 0--s ) {
148                         m2 = (1<<(bit-s));
149                         m = (m2>>1);
150                         wm = powMod( g[s], p-2, p );
151                         for ( k = 0; k < n; k += m2 ) {
152                                 w = 1;
153                                 for ( j = 0; j < m; ++j ) {
154                                         t = ((LT)(w)) * a[k+j+m] % p;
155                                         u = a[ k + j ];
156                                         a[ k + j ] = ( u + t ) % p;
157                                         a[ k + j + m ] = ( u + p - t ) % p;
158                                         w = ( ((LT)w) * wm ) % p;
159                                 }
160                         }
161                 }
162                 inv = powMod( n, p-2, p );
163                 for ( k = 0; k < n; ++k ) {
164                         a[ k ] = ( ((LT)inv) * a[ k ] ) % p;
165                 }
166         }
167         void out( T e[] ) {
168                 int i;
169                 for ( i = 0; i < n; ++i ) {
170                         e[ i ] = a[ i ];
171                 }
172         }
173 
174         T a[ L ], g[ 100 ], p;
175         int n, bit;
176 };
177 
178 
179 #define  L  200009
180 typedef  long long Lint;
181 
182 FFT< L, int, Lint > fft;
183 
184 int a[ L ];
185 
186 int main() {
187         int td, n, m, t, i, p;
188         scanf( "%d"&td );
189         while ( td-- > 0 ) {
190                 scanf( "%d%d"&n, &m );
191                 for ( i = 0; i < n; ++i ) {
192                         scanf( "%d", a+i );
193                 }
194                 t = (n-1)*+ 1;
195                 fft.fft( a, n, t );
196                 p = fft.getP();
197                 for ( i = 0; i < n; ++i ) {
198                         a[ i ] = fft.powMod( a[ i ], m, p );
199                 }
200                 fft.ifft( a, n, n );
201                 for ( i = 0; i < t; ++i ) {
202                         printf( "[%d] = %d\n", i, a[ i ] );
203                 }
204                 printf( "\n" );
205         }
206         return 0;
207 }
208 


posted on 2011-04-05 22:37 coreBugZJ 阅读(1086) 评论(0)  编辑 收藏 引用 所属分类: ACM


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理