WA on #2
查看原帖
WA on #2
762646
Piggy343288楼主2023/4/23 14:13
#include <bits/stdc++.h>
using namespace std;

template <typename T>
void read(T& x) {
    x = 0;
    char c(getchar());
    int f(1);
    for (; !isdigit(c); c = getchar())
        if (c == '-')
            f = -1;
    for (; isdigit(c); c = getchar())
        x = (x * 10) + (c ^ 48);
    x *= f;
}

const int maxn = 6e5 + 5;
const int maxm = maxn << 1;
const int mod = 998244353;
const int g = 3, invg = 332748118;
typedef int room[maxn];

int n, m;

template <int mod>
struct typemod {
    int val;
    typemod(int a = 0) : val(a) {}
    int inc(int a, int b) const { return a = (a+b)%mod; }
    int dec(int a, int b) const { return a = ((a-b)%mod+mod)%mod; }
    int mul(int a, int b) const { return (__int128)1 * a * b % mod; }
    typemod<mod> operator+(const typemod<mod>& x) const {
        return typemod(inc(val, x.val));
    }
    typemod<mod> operator-(const typemod<mod>& x) const {
        return typemod(dec(val, x.val));
    }
    typemod<mod> operator*(const typemod<mod>& x) const {
        return typemod(mul(val, x.val));
    }
    typemod<mod>& operator+=(const typemod<mod>& x) {
        *this = *this + x;
        return *this;
    }
    typemod<mod>& operator-=(const typemod<mod>& x) {
        *this = *this - x;
        return *this;
    }
    typemod<mod>& operator*=(const typemod<mod>& x) {
        *this = *this * x;
        return *this;
    }
    int operator==(const typemod<mod>& x) const { return x.val == val; }
    int operator!=(const typemod<mod>& x) const { return x.val != val; }
};

typedef typemod<mod> Tm;
int rev[maxn];
int getrev(int x) {
    int lim_ = 1, len = 0;
    while (lim_ <= x)
        lim_ <<= 1, ++len;
    for (int i = 1; i < lim_; ++i)
        rev[i] = rev[i >> 1] >> 1 | ((i & 1) << (len - 1));
    return lim_;
}
struct Poly {
    int lim_, len;
    typedef vector<Tm> vtm;
    vtm a;
    int n;
    void resize(int x) { a.resize(x + 1); n=x;}
    Tm qpow(Tm x, int mi) {
        Tm res(1);
        while (mi) {
            if (mi & 1)
                res = res * x;
            mi >>= 1;
            x = x * x;
        }
        return res;
    }
    int qpow(int x, int mi) {
        int res(1);
        while (mi) {
            if (mi & 1)
                res = 1ll * res * x % mod;
            mi >>= 1;
            x = 1ll * x * x % mod;
        }
        return res;
    }

    void NTT(vtm& A, int opt, int lim = -1) {
        if (!~lim)
            lim = lim_;
        A.resize(lim);
        for (int i = 0; i < lim; ++i)
            if (i < rev[i])
                swap(A[i], A[rev[i]]);
        for (int mid = 1; mid < lim; mid <<= 1) {
            Tm gn = qpow((opt == 1) ? g : invg, (mod - 1) / (mid << 1));
            for (int j = 0; j < lim; j += (mid << 1)) {
                Tm w(1);
                for (int k(0); k < mid; k += 1, w = w * gn) {
                    Tm x = A[j + k], y = A[j + k + mid] * w;
                    A[j + k] = x + y;
                    A[j + k + mid] = x - y;
                }
            }
        }
        if (opt != 1) {
            Tm z = qpow(Tm(lim), mod - 2);
            for (int i = 0; i < lim; ++i)
                A[i] = A[i] * z;
        }
    }
    void NTT(Poly& A, int opt, int lim = -1) {
        if (!~lim)
            lim = lim_;
        NTT(A.a, opt, lim);
    }
    void inv(const Poly& F, Poly& G1, int x) {
        if (x == 1)
            return G1.a[0] = qpow(F.a[0], mod - 2), void();
        inv(F, G1, (x + 1) >> 1);
        Poly c = F;
        lim_=getrev(x << 1);
        c.resize(lim_);
        for (int i = x; i < lim_; ++i)
            c.a[i] = 0;
        NTT(c.a, 1), NTT(G1.a, 1);
        for (int i = 0; i < lim_; ++i)
            G1.a[i] = (Tm(2) - c.a[i] * G1.a[i]) * G1.a[i];
        NTT(G1.a, -1);
        for (int i = x; i < lim_; ++i)
            G1.a[i] = 0;
    }
    Poly Inv() {
        Poly ans;
        ans.resize(0);
        inv(*this, ans, n + 1);
        ans.n = (*this).n;
        return ans;
    }
    Poly Deri() {
        Poly z = *this;
        for (int i = 1; i <= z.n; ++i)
            z.a[i - 1] = z.a[i] * i;
        z.a[z.n] = 1;
        z.n > 0 ? --z.n : 0;
        return z;
    }
    Poly reward() {
        Poly z = *this;
        z.resize(z.n + 1);
        for (int i = z.n; ~i; --i)
            z.a[i + 1] = z.a[i] * qpow(Tm(i + 1), mod - 2);
        z.a[0] = 0;
        return z;
    }
    Poly Ln() {
        Poly F = *this, ans = (*this).Inv();
        F = F.Deri();
        lim_=getrev((*this).n << 1);
        NTT(F, 1), NTT(ans, 1);
        for (int i = 0; i < lim_; ++i)
            ans.a[i] = ans.a[i] * F.a[i];
        NTT(ans, -1);
        ans = ans.reward();
        ans.n = (*this).n;
        return ans;
    }
    Poly operator*(const Poly& z) {
        Poly X = *this, Y = z;
        X.n += z.n;
        getrev(X.n);
        NTT(X.a, 1), NTT(Y.a, 1);
        for (int i = 0; i < lim_; ++i)
            X.a[i] *= Y.a[i];
        NTT(X.a, -1);
        return X;
    }
    Poly& operator*=(Poly& z) { return *this = *this * z; }
    void Exp(Poly& F, Poly& G, int x) {
        if (x == 1) {
        	G.resize(1);
            G.a[0] = 1;
        } else {
            Exp(F, G, (x + 1) >> 1);
            Poly LnG=G.Ln();
            LnG.resize(G.n);
            for (int i = 0; i <= LnG.n; i++) {
                LnG.a[i] = F.a[i]-LnG.a[i];
            }
            LnG.a[0] += 1;
            G *= LnG;
            G.resize(1+(LnG.n<<1));
        }
    }
    Poly Exp() {
        Poly z = *this;
        z.resize(z.n + 1);
        Exp(*this, z, n);
        return z;
    }
} F, G;

signed main() {
    read(F.n);
    F.n--;
    F.resize(F.n);
    int n=F.n;
    for (int i = 0; i <= F.n; ++i)
        read(F.a[i]);
    F = F.Exp();
    for (int i = 0; i <= n; ++i)
        printf("%d ", F.a[i]);
    return 0;
}

rt,经过坚持不懈的奋斗,调到了90pts,但是WA on #2求助

2023/4/23 14:13
加载中...