# coreBugZJ

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

Problem 2017 Hwh’s Problem

## 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.

2
2 2
3 2
2 3
3 2

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

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

## Source

FOJ有奖月赛-2011年03月

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