QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#610326#6811. Alice's DollstosaniaRE 0ms0kbC++148.7kb2024-10-04 15:36:342024-10-04 15:36:36

Judging History

你现在查看的是最新测评结果

  • [2024-10-04 15:36:36]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-10-04 15:36:34]
  • 提交

answer

//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;

const int N = 300007;
const int gg = 3, ig = 332738118, img = 86583718;
const int mod = 998244353;

template <typename T>void read(T &x)
{
    x = 0;
    int f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-')f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    x *= f;
}

ll qpow(ll a, ll b)
{
    ll res = 1;
    while (b) {
        if (b & 1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return res;
}

namespace Poly
{
#define mul(x, y) (1ll * x * y >= mod ? 1ll * x * y % mod : 1ll * x * y)
#define minus(x, y) (1ll * x - y < 0 ? 1ll * x - y + mod : 1ll * x - y)
#define plus(x, y) (1ll * x + y >= mod ? 1ll * x + y - mod : 1ll * x + y)
#define ck(x) (x >= mod ? x - mod : x)//取模运算太慢了

typedef vector<int> poly;
const int G = 3;//根据具体的模数而定,原根可不一定不一样!!!
//一般模数的原根为 2 3 5 7 10 6
const int inv_G = qpow(G, mod - 2);
int RR[N], deer[2][23][N], inv[N];

void init(const int t) {//预处理出来NTT里需要的w和wn,砍掉了一个log的时间
    for (int p = 1; p <= t; ++ p) {
        int buf1 = qpow(G, (mod - 1) / (1 << p));
        int buf0 = qpow(inv_G, (mod - 1) / (1 << p));
        deer[0][p][0] = deer[1][p][0] = 1;
        for (int i = 1; i < (1 << p); ++ i) {
            deer[0][p][i] = 1ll * deer[0][p][i - 1] * buf0 % mod;//逆
            deer[1][p][i] = 1ll * deer[1][p][i - 1] * buf1 % mod;
        }
    }
    inv[1] = 1;
    for (int i = 2; i <= (1 << t); ++ i)
        inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;
}

int NTT_init(int n) {//快速数论变换预处理
    int limit = 1, L = 0;
    while (limit <= n) limit <<= 1, L ++ ;
    for (int i = 0; i < limit; ++ i)
        RR[i] = (RR[i >> 1] >> 1) | ((i & 1) << (L - 1));
    return limit;
}

void NTT(poly &A, int type, int limit) {//快速数论变换
    A.resize(limit);
    for (int i = 0; i < limit; ++ i)
        if (i < RR[i])
            swap(A[i], A[RR[i]]);
    for (int mid = 2, j = 1; mid <= limit; mid <<= 1, ++ j) {
        int len = mid >> 1;
        for (int pos = 0; pos < limit; pos += mid) {
            int *wn = deer[type][j];
            for (int i = pos; i < pos + len; ++ i, ++ wn) {
                int tmp = 1ll * (*wn) * A[i + len] % mod;
                A[i + len] = ck(A[i] - tmp + mod);
                A[i] = ck(A[i] + tmp);
            }
        }
    }
    if (type == 0) {
        for (int i = 0; i < limit; ++ i)
            A[i] = 1ll * A[i] * inv[limit] % mod;
    }
}

poly poly_mul(poly A, poly B) {//多项式乘法
    int deg = A.size() + B.size() - 1;
    int limit = NTT_init(deg);
    poly C(limit);
    NTT(A, 1, limit);
    NTT(B, 1, limit);
    for (int i = 0; i < limit; ++ i)
        C[i] = 1ll * A[i] * B[i] % mod;
    NTT(C, 0, limit);
    C.resize(deg);
    return C;
}

poly poly_inv(poly &f, int deg) {//多项式求逆
    if (deg == 1)
        return poly(1, qpow(f[0], mod - 2));

    poly A(f.begin(), f.begin() + deg);
    poly B = poly_inv(f, (deg + 1) >> 1);
    int limit = NTT_init(deg << 1);
    NTT(A, 1, limit), NTT(B, 1, limit);
    for (int i = 0; i < limit; ++ i)
        A[i] = B[i] * (2 - 1ll * A[i] * B[i] % mod + mod) % mod;
    NTT(A, 0, limit);
    A.resize(deg);
    return A;
}

poly poly_dev(poly f) {//多项式求导
    int n = f.size();
    for (int i = 1; i < n; ++ i) f[i - 1] = 1ll * f[i] * i % mod;
    return f.resize(n - 1), f;//f[0] = 0,这里直接扔了,从1开始
}

poly poly_idev(poly f) {//多项式求积分
    int n = f.size();
    for (int i = n - 1; i ; -- i) f[i] = 1ll * f[i - 1] * inv[i] % mod;
    return f[0] = 0, f;
}

poly poly_ln(poly f, int deg) {//多项式求对数
    poly A = poly_idev(poly_mul(poly_dev(f), poly_inv(f, deg)));
    return A.resize(deg), A;
}

poly poly_exp(poly &f, int deg) {//多项式求指数
    if (deg == 1)
        return poly(1, 1);

    poly B = poly_exp(f, (deg + 1) >> 1);
    B.resize(deg);
    poly lnB = poly_ln(B, deg);
    for (int i = 0; i < deg; ++ i)
        lnB[i] = ck(f[i] - lnB[i] + mod);

    int limit = NTT_init(deg << 1);//n -> n^2
    NTT(B, 1, limit), NTT(lnB, 1, limit);
    for (int i = 0; i < limit; ++ i)
        B[i] = 1ll * B[i] * (1 + lnB[i]) % mod;
    NTT(B, 0, limit);
    B.resize(deg);
    return B;
}

poly poly_sqrt(poly &f, int deg) {//多项式开方
    if (deg == 1) return poly(1, 1);
    poly A(f.begin(), f.begin() + deg);
    poly B = poly_sqrt(f, (deg + 1) >> 1);
    poly IB = poly_inv(B, deg);
    int limit = NTT_init(deg << 1);
    NTT(A, 1, limit), NTT(IB, 1, limit);
    for (int i = 0; i < limit; ++ i)
        A[i] = 1ll * A[i] * IB[i] % mod;
    NTT(A, 0, limit);
    for (int i = 0; i < deg; ++ i)
        A[i] = 1ll * (A[i] + B[i]) * inv[2] % mod;
    A.resize(deg);
    return A;
}

poly poly_pow(poly f, int k) {//多项式快速幂
    f = poly_ln(f, f.size());
    for (auto &x : f) x = 1ll * x * k % mod;
    return poly_exp(f, f.size());
}

poly poly_cos(poly f, int deg) {//多项式三角函数(cos)
    poly A(f.begin(), f.begin() + deg);
    poly B(deg), C(deg);
    for (int i = 0; i < deg; ++ i)
        A[i] = 1ll * A[i] * img % mod;

    B = poly_exp(A, deg);
    C = poly_inv(B, deg);
    int inv2 = qpow(2, mod - 2);
    for (int i = 0; i < deg; ++ i)
        A[i] = 1ll * (1ll * B[i] + C[i]) % mod * inv2 % mod;
    return A;
}

poly poly_sin(poly f, int deg) {//多项式三角函数(sin)
    poly A(f.begin(), f.begin() + deg);
    poly B(deg), C(deg);
    for (int i = 0; i < deg; ++ i)
        A[i] = 1ll * A[i] * img % mod;

    B = poly_exp(A, deg);
    C = poly_inv(B, deg);
    int inv2i = qpow(img << 1, mod - 2);
    for (int i = 0; i < deg; ++ i)
        A[i] = 1ll * (1ll * B[i] - C[i] + mod) % mod * inv2i % mod;
    return A;
}

poly poly_arcsin(poly f, int deg) {
    poly A(f.size()), B(f.size()), C(f.size());
    A = poly_dev(f);
    B = poly_mul(f, f);
    for (int i = 0; i < deg; ++ i)
        B[i] = minus(mod, B[i]);
    B[0] = plus(B[0], 1);
    C = poly_sqrt(B, deg);
    C = poly_inv(C, deg);
    C = poly_mul(A, C);
    C = poly_idev(C);
    return C;
}

poly poly_arctan(poly f, int deg) {
    poly A(f.size()), B(f.size()), C(f.size());
    A = poly_dev(f);
    B = poly_mul(f, f);
    B[0] = plus(B[0], 1);
    C = poly_inv(B, deg);
    C = poly_mul(A, C);
    C = poly_idev(C);
    return C;
}
}
using Poly::poly;
using Poly::poly_inv;
using Poly::poly_mul;
using Poly::poly_arcsin;
using Poly::poly_arctan;

ll n, m, x, k, type, p, q, jie[N], inv[N],njie[N];
poly f, g;
char s[N];
poly a;
poly solve_a(int l, int r) {
    //cout<<l<<" "<<r<<endl;
    if (r - l == 1){
        if (l == 0){
            return poly{1};
        }
        else
            return poly{l, 1};
    }
        
    int mid = (l + r) / 2;

    return poly_mul(solve_a(l, mid) , solve_a(mid, r)) ;
}
signed main()
{
    Poly::init(22);//2^21 = 2,097,152,根据题目数据多项式项数的大小自由调整,注意大小需要跟deer数组同步(21+1=22)

    read(n);
    read(m);
    {
        int a, b;
        read(a);
        read(b);
        p = a * qpow(b, mod - 2) % mod;
        q = (1 - p + mod) % mod;
    }
    jie[0] = 1;
    njie[0]=1;
    for (int i = 1; i <= n+m; i++) {
        jie[i] = jie[i - 1] *i%mod;
        njie[i]=njie[i-1]*n%mod;
    }
    inv[n+m] = qpow(jie[n+m], mod - 2);
    for (int i = n+m - 1; i >= 1; i--)
    {
        inv[i] = inv[i + 1] * (i+1) % mod;
    }
    inv[0]=1;
    a = solve_a(0, n);
    for (int i = 0; i <= n - 1; i++) {
        a[i] *= inv[n - 1];
        a[i] %= mod;
    }
    reverse(a.begin(), a.end());
    poly s;
    s.resize(n + m);
    for (int i = 0; i < n + m; i++) {
        s[i] = q * inv[i];
    }
    for (int i = 0; i < n + m; i++) {
        if (i == 0)
            s[i] = (1 - s[i]+mod)%mod;
        else s[i] = (-s[i]+mod)%mod;
    }
    s = poly_inv(s, n + m);
    for (int i = 0; i < n + m; i++) {
        s[i] = (s[i] * jie[i]) % mod;
    }
    poly w = poly_mul(s, a);
    for (int i = 0; i <= m; i++) {
        w[i] = w[i + n - 1];
    }
    w.resize(m+1);
    poly ans, op;
    op.resize(m + 1);
    for (int i = 0; i <= m; i++) {
        op[i] = njie[i] * inv[i] % mod;
        w[i] *= inv[i];
        w[i]%=mod;
    }
    ans = poly_mul(op, w);
    int A=qpow(p, n);
    for (int i = 0; i <= m; i++) {
        cout << ans[i]*jie[i] % mod*A % mod << "\n";
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

1 3 1 2

output:


result: