XSY 2263 - Grasshoppers

题目精选 FFT 生成函数

分析

  每次变换的意义相当于: 生成函数在循环卷积的意义下, 乘上 $2x^{-1}+1$ . 所以求出 $(2x^{-1}+1)^T$ 即可.

实现

FFT注意事项:
1. 变换过去就变换不回来了.
2. 如果精度要求不高, 那么就是用 round, 否则使用 (int)(x+0.5) , 但是这样只能用于 正数 .

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
#define F(i,a,b) for (int i=(a);i<=(b);i++)
#define LL long long
#define LD long double
const int N=300000;
const LD PI=acos(-1);
int n,m,t;
int a[N];
struct Comp {
    LD x,y;
    Comp(LD _x=0,LD _y=0):x(_x),y(_y) {}
    friend Comp operator + (Comp a,Comp b) { return Comp(a.x+b.x,a.y+b.y); }
    friend Comp operator - (Comp a,Comp b) { return Comp(a.x-b.x,a.y-b.y); }
    friend Comp operator * (Comp a,Comp b) { return Comp(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x); }
}B[N],C[N],A[N];
int bit,len;
int rev[N];
Comp wi[N],wv[N];
int rd(void) {
    int f=1; char c=getchar(); for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
    int x=0; for (;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;
}
void Init(int siz) {
    for (bit=0,len=1;len<siz;bit++,len<<=1);
    for (int i=0;i<len;i++) rev[i]=rev[i>>1]>>1|(i&1)<<(bit-1);
    for (int i=1,k=(1<<i);i<=bit;k=(1<<++i)) {
        wi[k]=Comp(cos(2*PI/+k),sin(2*PI/+k));
        wv[k]=Comp(cos(2*PI/-k),sin(2*PI/-k));
    }
}
void FFT(Comp *A,int sign) {
    for (int i=0;i<len;i++) if (i<rev[i]) swap(A[i],A[rev[i]]);
    for (int i=2;i<=len;i<<=1) {
        Comp wn=( sign==+1?wi[i]:wv[i] );
        for (int j=0;j<len;j+=i) {
            Comp w(1,0);
            for (int k=0;k<i/2;k++) {
                Comp x=A[j+k], y=w*A[j+k+i/2];
                A[j+k]=x+y, A[j+k+i/2]=x-y;
                w=w*wn;
            }
        }
    }
    if (sign==-1)
        for (int i=0;i<len;i++)
            A[i]=Comp(A[i].x/len,0);
}
void Transfer(Comp *A) {
    static int tmp[N];
    for (int i=0;i<n;i++)
        tmp[i]=( (LL)round(A[i].x)+(LL)round(A[i+n].x) )%m;
    for (int i=0;i<len;i++)
        A[i]=(i<n?tmp[i]:0);
}
int T(double x) { return (((int)round(x)-1)%m+m)%m+1; }
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("A.in","r",stdin);
    #endif
    n=rd(),m=rd(),t=rd(); F(i,1,n) a[i]=rd();
    Init((n-1)+(n-1)+1);
    B[0]=C[0]=-1, B[n-1]=C[n-1]=2; t--;
    for (;t>0;t>>=1) {
        static Comp tmp[N]; memcpy(tmp,B,sizeof B);
        FFT(tmp,+1);
        if (t%2==1) {
            FFT(C,+1);
            for (int i=0;i<len;i++) C[i]=C[i]*tmp[i];
            FFT(C,-1);
            Transfer(C);
        }
        FFT(B,+1);
        for (int i=0;i<len;i++) B[i]=B[i]*tmp[i];
        FFT(B,-1);
        Transfer(B);
    }
    F(i,1,n) A[i%n]=a[i];
    FFT(A,+1);
    FFT(C,+1);
    for (int i=0;i<len;i++) A[i]=A[i]*C[i];
    FFT(A,-1);
    Transfer(A);
    F(i,1,n) printf("%d ",T(A[i%n].x)); printf("\n");
    return 0;
}