少女输出问题（II）-------（FFT）

Time Limit: 5000 MS Memory Limit: 65536 KB

FFT

来源：swust power oj 2540 少女输出问题（II）

Description

浩姐发现大魔王居然没被砍死，于是换了把更长的剑和更长的剑法，再看看输出效果吧……

Input

第一行：两个整数n,m（1 <= n ,m <= 100,000）。代表两个离散序列的长度。
第二行：n个整数A[i](1 <= A[i] <= 100)。代表第一个离散序列。
第三行：m个整数A[i](1 <= B[i] <= 100)。代表第二个离散序列。
给定的两个序列的第一位都是在0位置！未给出的部分的值都是0！

Output

一行：若干个数用空格隔开，为第一个序列卷积第二个序列的非零值部分，请不要输出多余的空格，并且请在行位加上换行符

Sample Input

3
3
1 1 1
1 1 1

Sample Output

1 2 3 2 1

题意：

这是一个中文题......

解题思路：

阳哥的FFT模板......
FFT是啥？------快速傅里叶变换......
你会吗？你不会！！！！呵呵哒~~

完整代码：

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define MAXN 400000
const double pi=acos(-1.0);
struct Complex
{
    double R, I;
    inline Complex(double real = 0.0, double image = 0.0)
    {
        R=real,I=image;
    }
    inline Complex operator+(Complex const &b) const
    {
        return Complex(R+b.R,I+b.I);
    }
    inline Complex operator-(Complex const &b) const
    {
        return Complex(R-b.R,I-b.I);
    }
    inline Complex operator*(Complex const &b) const
    {
        return Complex(R*b.R-I*b.I,I*b.R+R*b.I);
    }
};
inline int turn(int n)
{
    int i=1;
    for(;i<n;i<<=1);
    return i;
}
void Change(Complex y[],int len)
{
    int i,j,k;
    for(i=1,j=len/2;i<len-1;i++)
    {
        if(i<j)
            swap(y[i],y[j]);
        k=len/2;
        while(j>=k)
        {
            j-=k;
            k/=2;
        }
        if(j<k)j+=k;
    }
}
void FFT(Complex P[],int n,int op)
{
    Change(P,n);
    for(int len=2;len<=n;len<<=1)
    {
        int m=len>>1;
        Complex unit=Complex(cos(pi/m*op),sin(pi/m*op));
        for(int i=0;i<n;i+=len)
        {
            Complex W=Complex(1,0);
            for(int j=0;j<m;j++,W=W*unit)
            {
                Complex p=P[i+j],q=P[i+j+m];
                P[i+j]=p+W*q;
                P[i+j+m]=p-W*q;
            }
        }
    }
}
Complex A[MAXN], B[MAXN];
char s[MAXN];
int ans[MAXN];
int main()
{
    int n, m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(A,0,sizeof(A));
        memset(B,0,sizeof(B));
        for(int i=0;i<n;i++)
            scanf("%lf",&A[i].R);
        for(int i=0;i<m;i++)
            scanf("%lf",&B[i].R);
        n=max(n,m);
        n=turn(n);
        FFT(A,n<<1,1);
        FFT(B,n<<1,1);
        for(int i=0;i<(n<<1);i++)
            A[i]=A[i]*B[i];
        FFT(A,n<<1,-1);
        for(int i=0;i<(n<<1);i++)
        {
            int ans=A[i].R/(n<<1)+0.5;
            if(ans)
            {
                if(i)
                    printf(" ");
                printf("%d", ans);
            }
            else
            {
                printf("\n");
                break;
            }
        }
    }
    return 0;
}