云速建站怎么样,郑州市建设局官方网站,天津科技网站,了解目前网站建设情况FFT模版题。 观察题目#xff0c;我们可以发现#xff0c;只要把序列b倒过来#xff0c;再联想一下乘法运算。。。 我们会发现#xff0c;将序列a和序列b当作100进制数#xff0c;做一次乘法#xff0c;然后从低到高每一位便是答案了#xff08;乘完无需进位#xff09…FFT模版题。 观察题目我们可以发现只要把序列b倒过来再联想一下乘法运算。。。 我们会发现将序列a和序列b当作100进制数做一次乘法然后从低到高每一位便是答案了乘完无需进位 #include cstdio
#include cstdlib
#include cstring
#include cmath
#include algorithm
#include iostream
#include cctype
#include complex
#define rep(i, l, r) for(int il; ir; i)
#define down(i, l, r) for(int il; ir; i--)
#define maxn 400009
#define cd complex double
#define PI acos(0.0)*2.0
#define ll long long
using namespace std;
inline int read()
{int x0, f1; char chgetchar();while (!isdigit(ch)) {if (ch-) f-1; chgetchar();}while (isdigit(ch)) xx*10ch-0, chgetchar();return x*f;
}
cd a[maxn], b[maxn], c[maxn], A[maxn];
int n, m, n1[maxn], n2[maxn], s[maxn];
int ans[maxn];void fft(cd *a, bool flag)
{rep(i, 0, n-1) s[i]0;for(int i1, jn; in; i*2, j/2) rep(h, j/2, j-1) s[h]i;for(int i1; in; i*2) rep(j, 0, i-1) s[ji]s[j];rep(i, 0, n-1) A[i]a[s[i]];double piflag?PI:-PI;for(int step1; stepn; step*2){cd eexp(cd(0, 2.0*pi/double(step*2))), wcd(1, 0);for (int pos0; posstep; pos, w*e) for(int ipos; in; istep*2){cd retA[i], recw*A[istep];A[i]retrec, A[istep]ret-rec;}}if (!flag) rep(i, 0, n-1) A[i]/n;rep(i, 0, n-1) a[i]A[i];
}int main()
{mread(); rep(i, 1, m) n1[m-i]read(), n2[i-1]read();n1; while (nm*2) n*2;rep(i, 0, n-1) a[i]cd(n1[i], 0); fft(a, true);rep(i, 0, n-1) b[i]cd(n2[i], 0); fft(b, true);rep(i, 0, n-1) c[i]a[i]*b[i]; fft(c, false);rep(i, 0, m-1) ans[i]c[i].real()0.5;down(i, m-1, 0) printf(%d\n, ans[i]);
} 转载于:https://www.cnblogs.com/NanoApe/p/4479405.html
