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月
全整數(shù) FFT 加速整系數(shù)多項式乘法，不能僅僅套模板，需要對 FFT 有一點點理解。。。
1953ms 1796KB
1 #include <iostream>
2 #include <cstdio>
3
4 using namespace std;
5
6 template< int L, class T = int, class 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*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*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( 21, 211812353 );
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)*m + 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