自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 22:08:51，当前版本为作者最后更新于2019-03-17 00:20:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

大名鼎鼎的欧拉公式

$$\text e^{\text ix}=\cos x+ \text i\sin x$$

把这个式子稍微变形一下

$$\text e^{-\text ix}=\cos x-\text i\sin x$$

将这两个式子相加或相减一下，得到

$$2\cos x= \text e^{\text ix}+ \text e^{-\text ix}$$ $$2\text i\sin x=\text e^{ix}-\text e^{-\text ix}$$

然后我们移个项，并用 $F(x)$ 代换 $x$，就得出了结果

$$\cos F(x)=\frac{\text e^{\text iF(x)}+\text e^{-\text iF(x)}}{2} $$$$\sin F(x)=\frac{\text e^{\text iF(x)}-\text e^{-\text iF(x)}}{2\text i} $$

可是这里还有个虚数单位 $\text i$ 呢。。这怎么取模啊 QAQ
别慌，我们冷静分析一下

虚数单位 $\text i$ 实际上就是 $\omega_4$，也就是 $g^{(p-1)/4}$，在模 $p$ 下就等于 $86583718$。

剩下的，就是套上一个多项式指数函数的板子了。
Code：

#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize (2)
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 262147
#define ll long long
#define reg register
#define p 998244353
#define add(x,y) (x+y>=p?x+y-p:x+y)
#define dec(x,y) (x<y?x-y+p:x-y)
using namespace std;

inline int power(int a,int t){
	int res = 1;
	while(t){
		if(t&1) res = (ll)res*a%p;
		a = (ll)a*a%p;
		t >>= 1; 
	}
	return res;
}

inline void read(int &x){
    x = 0;
    char c = getchar();
    while(c<'0'||c>'9') c = getchar();
    while(c>='0'&&c<='9'){
        x = (x<<3)+(x<<1)+(c^48);
        c = getchar();
    }
}

void print(int x){
    if(x>9) print(x/10);
    putchar(x%10+'0');
}

int rev[N],rt[N],inv[N],inv2[N];
int siz;

void init(int n){
    int w,lim = 1;
    while(lim<=n) lim <<= 1,++siz;
    for(reg int i=1;i!=lim;++i) rev[i] = (rev[i>>1]>>1)|((i&1)<<(siz-1));
    inv2[1] = inv[1] = rt[lim>>1] = 1;
    w = power(114514,(p-1)>>siz); //114514 也是 998244353 的原根
    for(reg int i=(lim>>1)+1;i!=lim;++i) rt[i] = (ll)rt[i-1]*w%p;
    for(reg int i=(lim>>1)-1;i;--i) rt[i] = rt[i<<1];
    for(reg int i=2;i<=n;++i) inv[i] = (ll)(p-p/i)*inv[p%i]%p;
    for(reg int i=1;i<=siz;++i) inv2[1<<i] = p-((p-1)>>i);
}

inline int getlen(int n){
    return 1<<(32-__builtin_clz(n));
}

inline void NTT(int *f,int type,int lim){
    if(type==-1) reverse(f+1,f+lim);
    static unsigned long long a[N];
    reg int x,shift = siz-__builtin_ctz(lim);
    for(reg int i=0;i!=lim;++i) a[rev[i]>>shift] = f[i];
    for(reg int mid=1;mid!=lim;mid<<=1)
    for(reg int j=0;j!=lim;j+=(mid<<1))
    for(reg int k=0;k!=mid;++k){
        x = a[j|k|mid]*rt[mid|k]%p;
        a[j|k|mid] = a[j|k]-x+p;
        a[j|k] += x;
    } 
    for(reg int i=0;i!=lim;++i) f[i] = a[i]%p;
    if(type==1) return;
    x = inv2[lim];
    for(reg int i=0;i!=lim;++i) f[i] = (ll)f[i]*x%p;
}

inline void inverse(const int *f,int n,int *R){
    static int g[N],h[N],s[30];
    memset(g,0,getlen(n<<1)<<2);
    int lim = 1,top = 0;
    while(n){
        s[++top] = n;
        n >>= 1;
    }
    g[0] = power(f[0],p-2);
    while(top--){
        n = s[top+1];
        while(lim<=(n<<1)) lim <<= 1;
        memcpy(h,f,(n+1)<<2);
        memset(h+n+1,0,(lim-n)<<2);
        NTT(g,1,lim),NTT(h,1,lim);
        for(reg int i=0;i!=lim;++i) g[i] = g[i]*(2-(ll)g[i]*h[i]%p+p)%p;
        NTT(g,-1,lim);
        memset(g+n+1,0,(lim-n)<<2);
    }
    memcpy(R,g,(n+1)<<2);
}

inline void log(int *f,int n){
    static int g[N];
    int lim = getlen(n<<1);
    inverse(f,n,g);
    memset(g+n+1,0,(lim-n)<<2);
    for(reg int i=0;i!=n;++i) f[i] = (ll)f[i+1]*(i+1)%p;
    f[n] = 0;
    NTT(f,1,lim),NTT(g,1,lim);
    for(reg int i=0;i!=lim;++i) f[i] = (ll)f[i]*g[i]%p;
    NTT(f,-1,lim);
    for(reg int i=n;i;--i) f[i] = (ll)f[i-1]*inv[i]%p;
    f[0] = 0;
    memset(f+n+1,0,(lim-n)<<2);
}

inline void exp(const int *f,int n,int *R){
    static int g[N],h[N],s[30];
    int lim = 1,top = 0;
    memset(g,0,getlen(n<<1)<<2);
    while(n){
        s[++top] = n;
        n >>= 1;
    }
    g[0] = 1;
    while(top--){
        n = s[top+1];
        while(lim<=(n<<1)) lim <<= 1;
        memcpy(h,g,(n+1)<<2);
        memset(h+n+1,0,(lim-n)<<2);
        log(g,n);
        for(reg int i=0;i<=n;++i) g[i] = dec(f[i],g[i]);
        g[0] = add(g[0],1);
        NTT(g,1,lim),NTT(h,1,lim);
        for(reg int i=0;i!=lim;++i) g[i] = (ll)g[i]*h[i]%p;
        NTT(g,-1,lim);
        memset(g+n+1,0,(lim-n)<<2);
    }
    memcpy(R,g,(n+1)<<2);
}

#define img 86583718

inline void cos(const int *f,int n,int *R){
    static int g[N],h[N];
    for(reg int i=0;i<=n;++i) g[i] = (ll)f[i]*img%p;
    exp(g,n,g);
    inverse(g,n,h);
    for(reg int i=0;i<=n;++i) R[i] = 499122177ll*(g[i]+h[i])%p;
    
}

inline void sin(const int *f,int n,int *R){
    static int g[N],h[N];
    for(reg int i=0;i<=n;++i) g[i] = (ll)f[i]*img%p;
    exp(g,n,g);
    inverse(g,n,h);
    int x = power(img<<1,p-2);
    for(reg int i=0;i<=n;++i) R[i] = (ll)x*(g[i]-h[i]+p)%p;
}

#undef img;

int F[N];
int n,tp;

int main(){
    read(n),read(tp);
    init(n<<1|1);
    for(reg int i=0;i!=n;++i) read(F[i]);
    if(tp==0) sin(F,n-1,F);
    else cos(F,n-1,F);
    for(reg int i=0;i!=n;++i) print(F[i]),putchar(' ');
	return 0;	
}