提交记录 4411
提交时间 |
评测时间 |
2018-07-22 16:08:57 |
2020-07-31 23:00:47 |
#include<bits/stdc++.h>
#define pi acos(-1)
using namespace std;
complex<double> a[2621450],b[2621450];
int n,m,l,r[2621450];
void FFT(complex<double> *a,int f){
for(int i=0;i<n;i++)
if(i<r[i])
swap(a[i],a[r[i]]);
for(int i=1;i<n;i<<=1){
complex<double> wn(cos(pi/i),f*sin(pi/i));
int p=i<<1;
for(int j=0;j<n;j+=p){
complex<double> w(1,0);
for(int k=0;k<i;k++,w*=wn){
complex<double> x=a[j+k],y=w*a[j+k+i];
a[j+k]=x+y;
a[j+k+i]=x-y;
}
}
}
}
int main(){
cin>>n>>m;
for(int i=0;i<=n;i++)
cin>>a[i];
for(int i=0;i<=m;i++)
cin>>b[i];
m+=n;
for(n=1;n<=m;n<<=1)
l++;
for(int i=0;i<n;i++)
r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
FFT(a,1);
FFT(b,1);
for(int i=0;i<=n;i++)
a[i]*=b[i];
FFT(a,-1);
for(int i=0;i<=m;i++)
printf("%d ",int(a[i].real()/n+0.5));
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Subtask #1 Testcase #1 | 47.83 us | 56 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #2 | 242.132 ms | 10 MB + 484 KB | Accepted | Score: 100 | 显示更多 |
Subtask #1 Testcase #3 | 118.211 ms | 4 MB + 848 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #4 | 118.33 ms | 4 MB + 836 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #5 | 51.44 us | 56 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #6 | 50.39 us | 56 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #7 | 48.81 us | 56 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #8 | 205.905 ms | 10 MB + 216 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #9 | 205.826 ms | 10 MB + 216 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #10 | 169.661 ms | 9 MB + 972 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #11 | 241.415 ms | 10 MB + 564 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #12 | 243.473 ms | 9 MB + 444 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #13 | 46.7 us | 56 KB | Accepted | Score: 0 | 显示更多 |
Judge Duck Online | 评测鸭在线
Server Time: 2024-04-23 17:10:08 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用