Submission #978163
Source Code Expand
#include <cstdio>
int m;
int k;
typedef unsigned Zp;
const int mod = 1224736769;
const Zp root = 3;
Zp A[1<<18];
Zp B[1<<18];
Zp w[1<<17];
Zp y[1<<17];
Zp add(Zp lhs, Zp rhs){
Zp r = lhs + rhs;
if(r >= mod) return r - mod;
else return r;
}
Zp sub(Zp lhs, Zp rhs){
if(lhs >= rhs) return lhs - rhs;
else return mod + lhs - rhs;
}
Zp mul(Zp lhs, Zp rhs){
return ((long long) lhs * rhs) % mod;
}
Zp powr(Zp x, int n){
Zp r = 1;
for(; n; n>>=1){
if(n&0x1) r = mul(r, x);
x = mul(x, x);
}
return r;
}
Zp inv(Zp x){
return powr(x, mod-2);
}
unsigned clp2(unsigned x) {
x = x - 1;
x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >>16);
return x + 1;
}
void fft(Zp *A){
int u = 1;
int v = m/2;
for(int i=k;i>0;i--){
for(int jh=0;jh<u;jh++){
Zp wj = w[jh];
for(int j = jh << i, je = j|v;j<je; j++){
Zp Ajv = mul(wj, A[j|v]);
A[j|v] = sub(A[j], Ajv);
A[j] = add(A[j], Ajv);
}
}
u <<= 1;
v >>= 1;
}
}
void ifft(Zp *A){
int u = m/2;
int v = 1;
for(int i=1;i<=k;i++){
for(int jh=0;jh<u;jh++){
Zp wj = y[jh];
for(int j = jh << i, je = j|v;j<je; j++){
Zp Ajv = sub(A[j], A[j|v]);
A[j] = add(A[j], A[j|v]);
A[j|v] = mul(wj, Ajv);
}
}
u >>= 1;
v <<= 1;
}
}
void genwy(int i, int b, Zp z, Zp x){
if(b == 0) {
w[i] = z;
y[i] = x;
}
else {
genwy(i, b>>1, z, x);
genwy(i|b, b>>1, mul(z, w[b]), mul(x, y[b]));
}
}
int main(){
int n;
std::scanf("%d", &n);
for(int i=1;i<=n;i++){
int a, b;
std::scanf(" %d %d", &a, &b);
A[i] = a;
B[i] = b;
}
m = clp2(n+1) << 1;
k = __builtin_ctz(m);
Zp z=powr(root, (mod-1)/m);
Zp x=inv(z);
for(int j=m/4; j; j>>=1){
w[j] = z;
z = mul(z, z);
y[j] = x;
x = mul(x, x);
}
genwy(0, m/4, 1, 1);
fft(A);
fft(B);
for(int i=0;i<m;i++){
A[i] = mul(A[i], B[i]);
}
ifft(A);
Zp im = inv(m);
for(int i=1;i<=2*n;i++){
std::printf("%d\n", mul(A[i], im));
}
}
Submission Info
Submission Time |
|
Task |
C - 高速フーリエ変換 |
User |
ryuhei |
Language |
C++ (GCC 4.9.2) |
Score |
100 |
Code Size |
2219 Byte |
Status |
AC |
Exec Time |
184 ms |
Memory |
3748 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:101:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
std::scanf("%d", &n);
^
./Main.cpp:104:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
std::scanf(" %d %d", &a, &b);
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
100 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
00_sample_01 |
All |
00_sample_01, 01_00_01, 01_01_19, 01_02_31, 01_03_22, 01_04_31, 01_05_40, 01_06_15, 01_07_39, 01_08_28, 01_09_30, 01_10_23, 01_11_33, 01_12_11, 01_13_28, 01_14_41, 01_15_26, 01_16_49, 01_17_34, 01_18_02, 01_19_33, 01_20_29, 02_00_51254, 02_01_82431, 02_02_17056, 02_03_34866, 02_04_6779, 02_05_65534, 02_06_65535, 02_07_65536, 02_08_65537, 02_09_65538, 02_10_100000 |
Case Name |
Status |
Exec Time |
Memory |
00_sample_01 |
AC |
15 ms |
800 KB |
01_00_01 |
AC |
16 ms |
696 KB |
01_01_19 |
AC |
16 ms |
652 KB |
01_02_31 |
AC |
15 ms |
800 KB |
01_03_22 |
AC |
15 ms |
668 KB |
01_04_31 |
AC |
18 ms |
692 KB |
01_05_40 |
AC |
17 ms |
792 KB |
01_06_15 |
AC |
17 ms |
684 KB |
01_07_39 |
AC |
17 ms |
696 KB |
01_08_28 |
AC |
17 ms |
800 KB |
01_09_30 |
AC |
17 ms |
796 KB |
01_10_23 |
AC |
16 ms |
696 KB |
01_11_33 |
AC |
17 ms |
684 KB |
01_12_11 |
AC |
17 ms |
692 KB |
01_13_28 |
AC |
17 ms |
688 KB |
01_14_41 |
AC |
17 ms |
700 KB |
01_15_26 |
AC |
17 ms |
800 KB |
01_16_49 |
AC |
17 ms |
696 KB |
01_17_34 |
AC |
17 ms |
792 KB |
01_18_02 |
AC |
15 ms |
800 KB |
01_19_33 |
AC |
17 ms |
692 KB |
01_20_29 |
AC |
17 ms |
796 KB |
02_00_51254 |
AC |
97 ms |
2212 KB |
02_01_82431 |
AC |
163 ms |
3748 KB |
02_02_17056 |
AC |
47 ms |
1568 KB |
02_03_34866 |
AC |
80 ms |
2204 KB |
02_04_6779 |
AC |
27 ms |
800 KB |
02_05_65534 |
AC |
111 ms |
2208 KB |
02_06_65535 |
AC |
116 ms |
2208 KB |
02_07_65536 |
AC |
145 ms |
3744 KB |
02_08_65537 |
AC |
146 ms |
3676 KB |
02_09_65538 |
AC |
148 ms |
3676 KB |
02_10_100000 |
AC |
184 ms |
3740 KB |