//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "多项式乘法-快速傅里叶变换": {
        "prefix": "acm-7.4FFT",
        "body": [
            "struct Polynoial{",
            "    struct Complex{",
            "        double x,y;",
            "        Complex(double _x = 0.0,double _y = 0.0){",
            "            x = _x;",
            "            y = _y;",
            "        }",
            "        Complex operator-(const Complex &rhs) const{",
            "            return Complex(x-rhs.x,y-rhs.y);",
            "        }",
            "        Complex operator+(const Complex &rhs) const{",
            "            return Complex(x+rhs.x,y+rhs.y);",
            "        }",
            "        Complex operator*(const Complex &rhs) const{",
            "            return Complex(x*rhs.x-y*rhs.y,x*rhs.y+y*rhs.x);",
            "        }",
            "    };",
            "    ",
            "    int getSize(int n) {",
            "        int size = 1;",
            "        while (size < n) size <<= 1;",
            "        return size;",
            "    }",
            "    ",
            "    void change(vector<Complex>&a,int n){",
            "        for(int i = 1,j = n/2;i < n-1;i++){",
            "            if(i < j){",
            "                swap(a[i],a[j]);",
            "            }",
            "            int k = n/2;",
            "            while(j >= k){",
            "                j -= k;",
            "                k /= 2;",
            "            }",
            "            if(j < k)j += k;",
            "        }",
            "    }",
            "    ",
            "    void fft(vector<Complex>&a,int n,int opt){",
            "        change(a,n);",
            "        for(int h = 2;h <= n;h*=2){",
            "            Complex wn(cos(2*PI/h),sin(opt*2*PI/h));  // 修正：PI/h 而不是 PI/n",
            "            for(int j = 0;j < n;j+=h){",
            "                Complex w(1,0);",
            "                for(int k = j;k < j+h/2;k++){",
            "                    Complex u = a[k];",
            "                    Complex t = w*a[k+h/2];",
            "                    a[k]=u+t;",
            "                    a[k+h/2]=u-t;",
            "                    w=w*wn;",
            "                }",
            "            }",
            "        }",
            "        if(opt == -1){",
            "            for(int i = 0;i < n;i++){",
            "                a[i].x /= n;",
            "            }",
            "        }",
            "    }",
            "",
            "    vector<int> multiply(vector<int>& a, vector<int>& b) {",
            "        int size = getSize(a.size() + b.size() - 1);",
            "        ",
            "        vector<Complex> fa(size), fb(size);",
            "        for(int i = 0; i < (int)a.size(); i++) fa[i] = Complex(a[i], 0);",
            "        for(int i = 0; i < (int)b.size(); i++) fb[i] = Complex(b[i], 0);",
            "        for(int i = a.size(); i < size; i++) fa[i] = Complex(0, 0);",
            "        for(int i = b.size(); i < size; i++) fb[i] = Complex(0, 0);",
            "        ",
            "        fft(fa, size, 1);",
            "        fft(fb, size, 1);",
            "        ",
            "        for(int i = 0; i < size; i++) {",
            "            fa[i] = fa[i] * fb[i];",
            "        }",
            "        ",
            "        fft(fa, size, -1);",
            "        ",
            "        vector<int> res(size);",
            "        for(int i = 0; i < size; i++) {",
            "            res[i] = (int)(fa[i].x + 0.5);",
            "        }",
            "        return res;",
            "    }",
            "};"
        ],
        "description": "插入 多项式乘法-快速傅里叶变换"
    }
}