多项式 exp 可过样例 20pts 求调
查看原帖
多项式 exp 可过样例 20pts 求调
826774
Little_Fox_Fairy楼主2025/2/8 15:23

样例是对的,过了 1,2 两个点。

#include<bits/stdc++.h>
#define int long long 
using namespace std;
namespace fast_IO {
#define IOSIZE 100000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
const int N=4e5+10;

int n,m,e[N];
string s;
namespace Poly {
    const int mod=998244353;
    const int g=3;
    const int G=332748118;
    int tr[N];
    inline int qpow(int x,int y) {
        int res=1;
        while (y) {
            if (y&1) res=res*x%mod;
            x=x*x%mod,y>>=1;
        }
        return res;
    }
    inline void NTT(int len,int *a,bool op) {
        for (int i=0;i<len;i++) if (i<tr[i]) swap(a[i],a[tr[i]]);
        for (int k=2;k<=len;k<<=1) {
            int siz=k>>1,gen=qpow(op?g:G,(mod-1)/k);
            for (int i=0;i<len;i+=k) {
                int p=1;
                for (int l=i;l<i+siz;l++) {
                    int tmp=a[l+siz]*p%mod;
                    a[l+siz]=(a[l]-tmp+mod)%mod;
                    a[l]=(a[l]+tmp)%mod;
                    p=p*gen%mod;
                }
            }
        }
        if (op) return ;
        int inv=qpow(len,mod-2);
        for (int i=0;i<len;i++) a[i]=(a[i]*inv%mod+mod)%mod;
        return ; 
    }
    inline void Elaine(int *a,int *d,int n) {
        for (int i=1;i<n;i++) d[i-1]=i*a[i]%mod;
        d[n-1]=0;
        return ;
    }
    inline void Nephren(int *a,int *d,int n) {
        for (int i=1;i<n;i++) d[i]=a[i-1]*qpow(i,mod-2)%mod;
        d[0]=0;
        return ;
    }
    int tmp[N];
    inline void inv(int *F,int *G,int n) {
        if (n==1) {
            G[0]=qpow(F[0],mod-2);
            return ;
        }
        inv(F,G,(n+1)>>1);
        int len=1;while (len<=n+n) len<<=1;
        for (int i=1;i<len;i++) tr[i]=((tr[i>>1]>>1)|((i&1)?len>>1:0));
        for (int i=0;i<n;i++) tmp[i]=F[i];
        for (int i=n;i<len;i++) tmp[i]=0;
        NTT(len,tmp,1),NTT(len,G,1);
        for (int i=0;i<len;i++) G[i]=(2-G[i]*tmp[i]%mod+mod)%mod*G[i]%mod;
        NTT(len,G,0);
        for (int i=n;i<len;i++) G[i]=0;
        return ;
    }
    int b[N],d[N],res[N];
    inline void ln(int n,int a[]) {
        int len=1;while (len<=n+n) len<<=1;
        for (int i=0;i<len;i++) d[i]=b[i]=res[i]=0;
        Elaine(a,d,n);
        inv(a,b,n);
        for (int i=0;i<len;i++) tr[i]=((tr[i>>1]>>1)|((i&1)?len>>1:0));
        NTT(len,d,1),NTT(len,b,1);
        for (int i=0;i<len;i++) d[i]=d[i]*b[i]%mod;
        NTT(len,d,0);
        Nephren(d,res,n);
        for (int i=n;i<len;i++) res[i]=0;
        return ;
    }
    int tp[N],p[N];
    inline void exp(int n,int *a,int *b) {
        if (n==1) {
            b[0]=1;
            return ;
        }
        exp((n+1)>>1,a,b);
        ln(n,b);
        int len=1;while (len<=n+n) len<<=1;
        for (int i=0;i<len;i++) tr[i]=((tr[i>>1]>>1)|((i&1)?len>>1:0));
        for (int i=0;i<len;i++) tp[i]=a[i];
        NTT(len,b,1),NTT(len,tp,1),NTT(len,res,1);
        for (int i=0;i<len;i++) b[i]=(1ll-res[i]+tp[i]+mod)%mod*b[i]%mod;
        NTT(len,b,0);
        for (int i=n;i<len;i++) b[i]=0;
        return ;
    }
}using namespace Poly;
signed main() {
	cin>>n;int a[N],b[N];
    for (int i=0;i<n;i++) cin>>a[i];
    exp(n,a,b);
    for (int i=0;i<n;i++) cout<<b[i]<<" ";
	return (0-0);
}
2025/2/8 15:23
加载中...