Submission #6484646
Source Code Expand
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<math.h>
#include<complex.h>
#include<string.h>
#include <time.h>
#define lint long long
#define rep(i,n) for(lint i=0;i<(lint)(n);i++)
#define rrep(i,n) for(lint i=(lint)(n)-1;i>=0;i--)
#define repi(i,a,b) for(lint i=(lint)(a);i<(lint)(b);i++)
#define base 10
#define FREE(p) {free(p);p=NULL;}
struct ll{
complex* n;
lint deg;
};
struct ll init(lint x){
struct ll c;
c.deg=x;
c.n=(complex*)calloc(x,sizeof(complex));
return c;
}
struct ll make(char* x){
struct ll res=init(strlen(x));
rep(i,res.deg){
res.n[i]=x[res.deg-1-i]-'0';
}
return res;
}
struct ll make2(lint x){
struct ll res=init(log10(x)+1);
rep(i,res.deg){
res.n[i]=x%base;
x/=base;
}
return res;
}
struct ll resize(struct ll a,lint x){
struct ll c=init(x);
rep(i,a.deg){
c.n[i]=a.n[i];
}
return c;
}
struct ll fft(struct ll a){
if(a.deg==1){
return a;
}
lint n=a.deg;
struct ll a0=init(n/2);
struct ll a1=init(n/2);
rep(i,n/2){
a0.n[i]=a.n[i*2];
}
rep(i,n/2){
a1.n[i]=a.n[i*2+1];
}
struct ll inv_a0=fft(a0);
struct ll inv_a1=fft(a1);
struct ll inv_a=init(n);
complex zeta;
rep(i,n){
zeta=cos(2*M_PI*i/n)+I*sin(2*M_PI*i/n);
inv_a.n[i]=inv_a0.n[i%(n/2)]+zeta*inv_a1.n[i%(n/2)];
}
FREE(inv_a0.n);FREE(inv_a1.n);
return inv_a;
}
struct ll ifft(struct ll a){
lint n=a.deg;
struct ll b=fft(a);
struct ll res=init(a.deg);
rep(i,n)res.n[i]=b.n[(n-i)%n]/n;
FREE(b.n);
return res;
}
struct ll mul(struct ll a,struct ll b){
lint tmp=a.deg+b.deg-1;
lint n=1;
while(n<tmp)n<<=1;
struct ll _a=resize(a,n);
struct ll _b=resize(b,n);
struct ll inv_a=fft(_a);
struct ll inv_b=fft(_b);
struct ll inv_c=init(n);
rep(i,n){
inv_c.n[i]=inv_a.n[i]*inv_b.n[i];
}
struct ll c=ifft(inv_c);
FREE(_a.n);FREE(_b.n);
return c;
}
void debug(struct ll a){
lint* b=(lint*)calloc(a.deg+1,sizeof(lint*));
lint n=a.deg;
rep(i,n){
b[i]=(lint)round(creal(a.n[i]));
}
rep(i,n){
b[i+1]+=b[i]/base;
b[i]%=base;
}
bool f=0;
rrep(i,a.deg+1){
if(b[i]!=0)f=1;
if(f)printf("%lld",b[i]);
}
puts("");
FREE(b);
}
void print(FILE* file,struct ll a){
lint* b=(lint*)calloc(a.deg+1,sizeof(lint*));
lint n=a.deg;
rep(i,n){
b[i]=(lint)round(creal(a.n[i]));
}
rep(i,n){
b[i+1]+=b[i]/base;
b[i]%=base;
}
bool f=0;
rrep(i,a.deg+1){
if(b[i]!=0)f=1;
if(f)fprintf(file,"%lld",b[i]);
}
puts("");
FREE(b);
}
int main(){
lint n;
scanf("%lld",&n);
struct ll a=init(n);
struct ll b=init(n);
lint _a,_b;
rep(i,n){
scanf("%lld%lld",&_a,&_b);
a.n[i]=_a;b.n[i]=_b;
}
struct ll c=mul(a,b);
printf("%lld\n",(lint)round(creal(c.n[2*n-1])));
rep(i,2*n-1){
printf("%lld\n",(lint)round(creal(c.n[i])));
}
}
Submission Info
Submission Time
2019-07-21 12:55:38+0900
Task
C - 高速フーリエ変換
User
hotman78
Language
C (GCC 5.4.1)
Score
100
Code Size
3236 Byte
Status
AC
Exec Time
1763 ms
Memory
253916 KB
Compile Error
./Main.c: In function ‘main’:
./Main.c:132:5: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&n);
^
./Main.c:137:9: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld",&_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
5 ms
512 KB
01_00_01
AC
1 ms
128 KB
01_01_19
AC
1 ms
256 KB
01_02_31
AC
1 ms
256 KB
01_03_22
AC
1 ms
256 KB
01_04_31
AC
1 ms
256 KB
01_05_40
AC
1 ms
256 KB
01_06_15
AC
1 ms
128 KB
01_07_39
AC
1 ms
256 KB
01_08_28
AC
1 ms
256 KB
01_09_30
AC
1 ms
256 KB
01_10_23
AC
1 ms
256 KB
01_11_33
AC
1 ms
256 KB
01_12_11
AC
1 ms
128 KB
01_13_28
AC
1 ms
256 KB
01_14_41
AC
1 ms
256 KB
01_15_26
AC
1 ms
256 KB
01_16_49
AC
1 ms
256 KB
01_17_34
AC
1 ms
256 KB
01_18_02
AC
1 ms
128 KB
01_19_33
AC
1 ms
256 KB
01_20_29
AC
1 ms
256 KB
02_00_51254
AC
853 ms
120292 KB
02_01_82431
AC
1759 ms
251228 KB
02_02_17056
AC
405 ms
56684 KB
02_03_34866
AC
850 ms
119268 KB
02_04_6779
AC
94 ms
12920 KB
02_05_65534
AC
856 ms
121188 KB
02_06_65535
AC
854 ms
121188 KB
02_07_65536
AC
857 ms
121188 KB
02_08_65537
AC
1755 ms
250204 KB
02_09_65538
AC
1754 ms
252380 KB
02_10_100000
AC
1763 ms
253916 KB