Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #include<vector>
- #include<set>
- #include<queue>
- using namespace std;
- int n, m;
- vector<long long> res;
- using cd = complex<double>;
- const double PI = acos(-1);
- void fft(vector<cd> & a, bool invert) {
- int n = a.size();
- if (n == 1)
- return;
- vector<cd> a0(n / 2), a1(n / 2);
- for (int i = 0; 2 * i < n; i++) {
- a0[i] = a[2*i];
- a1[i] = a[2*i+1];
- }
- fft(a0, invert);
- fft(a1, invert);
- double ang = 2 * PI / n * (invert ? -1 : 1);
- cd w(1), wn(cos(ang), sin(ang));
- for (int i = 0; 2 * i < n; i++) {
- a[i] = a0[i] + w * a1[i];
- a[i + n/2] = a0[i] - w * a1[i];
- if (invert) {
- a[i] /= 2;
- a[i + n/2] /= 2;
- }
- w *= wn;
- }
- }
- vector<long long> multiply(vector<long long> const& a, vector<long long> const& b) {
- vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
- long long n = 1;
- while (n < a.size() + b.size())
- n <<= 1;
- fa.resize(n);
- fb.resize(n);
- fft(fa, false);
- fft(fb, false);
- for (long long i = 0; i < n; i++)
- fa[i] *= fb[i];
- fft(fa, true);
- vector<long long> result(n);
- for (long long i = 0; i < n; i++)
- result[i] = round(fa[i].real());
- return result;
- }
- int main(){
- int T;
- cin>>T;
- while (T--){
- cin>>n;
- vector<long long> v1(n+1, 0);
- vector<long long> v2(n+1, 0);
- for (int i = 0; i <=n; i++){
- cin>>m;
- v1.push_back(m);
- }
- for (int i = 0; i <=n; i++){
- cin>>m;
- v2.push_back(m);
- }
- reverse(v1.begin(), v1.end());
- reverse(v2.begin(), v2.end());
- res = multiply(v1, v2);
- for (int i = 0; i < 2*n + 1; i++){
- cout<<res[i]<<" ";
- }
- cout<<endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement