QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#402451#6811. Alice's DollsStarrykiller#WA 13ms10084kbC++233.6kb2024-04-30 16:34:112024-04-30 16:34:12

Judging History

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

  • [2024-04-30 16:34:12]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:10084kb
  • [2024-04-30 16:34:11]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define int long long 

constexpr int MAXN=4e6+10, p=998244353, G=3;
int qpow(int a, int n) {
    int res=1;
    while (n) {
        if (n&1) res=res*a%p;
        a=a*a%p; n>>=1;
    }
    return res;
}
#define inv(x) qpow(x,p-2)

signed rev[MAXN];
using poly=vector<int>;
istream& operator>>(istream& is, poly& f) {
    for (auto& i: f) cin>>i;
    return is;
}

poly ntt(const poly& a, int n, int sgn=1) {
    poly f=a; f.resize(n);
    int bit=__lg(n);
    for (int i=1; i<n; ++i)
        rev[i]=(rev[i>>1]>>1) | ((i&1)<<(bit-1));
    for (int i=1; i<n; ++i)
        if (i<rev[i]) swap(f[i],f[rev[i]]);
    for (int l=1, t=1; l<n; l<<=1, ++t) {
        int step=qpow(G,p-1+((p-1)>>t)*sgn);
        for (int j=0; j<n; j+=l<<1)
            for (int k=j, cur=1; k<j+l; ++k, cur=cur*step%p) {
                int g=f[k], h=cur*f[k+l]%p;
                f[k]=(g+h)%p, f[k+l]=(p+g-h)%p;
            }
    }
    if (sgn==-1) {
        int invn=inv(n);
        for (auto &i: f)
            i=i*invn%p;
    }
    return f;
}   

poly convolution(const poly& f, const poly& g) {
    int n=f.size(), m=g.size(); int N=1ll<<(__lg(n+m+1)+1);
    poly a=ntt(f,N), b=ntt(g,N);
    for (int i=0; i<N; ++i) a[i]=a[i]*b[i]%p;
    a=ntt(a,N,-1);
    a.resize(n+m-1);
    return a;
}

poly get_inv(const poly& f) {
    assert(f[0]%p);
    poly g(1); g[0]=inv(f[0]);
    int deg=1; int n=f.size();
    while (deg<n<<1) {
        int N=deg<<1;
        auto h=ntt(deg<=n?poly(f.begin(),f.begin()+deg):f,N); g=ntt(g,N);
        for (int i=0; i<N; ++i)
            g[i]=g[i]*(p+2-g[i]*h[i]%p)%p;
        g=ntt(g,N,-1); g.resize(deg);
        deg<<=1;
    }
    g.resize(n);
    return g;
}

poly get_deriv(const poly& f) {
    int n=f.size();
    auto g=poly(n);
    for (int i=0; i<n-1; ++i)
        g[i]=(i+1)*f[i+1]%p;
    return g;
}

poly get_integ(const poly& f) {
    int n=f.size();
    auto g=poly(n+1);
    for (int i=0; i<n; ++i)
        g[i+1]=f[i]*inv(i+1)%p;
    g[0]=0;
    return g;
}

poly get_ln(const poly& f) {
    int n=f.size();
    assert(f[0]==1);
    auto g=get_deriv(f), h=get_inv(f);
    g=convolution(g,h); g.resize(n);
    g=get_integ(g); g.resize(n);
    return g;
}

poly get_exp(const poly& f) {
    int n=f.size(); assert(!f[0]);
    int deg=1; poly g={1};
    while (deg<n<<1) {
        int N=deg<<1;
        auto lng=get_ln(g);
        for (int i=0; i<deg; ++i)
            lng[i]=(p+f[i]-lng[i])%p;
        lng[0]++;
        lng=ntt(lng,N); g=ntt(g,N);
        for (int i=0; i<N; ++i)
            g[i]=g[i]*lng[i]%p;
        g=ntt(g,N,-1); 
        deg<<=1; g.resize(deg); 
    }
    g.resize(n);
    return g;
}

poly qpow(const poly& f, int n) {
    auto g=get_ln(f);
    for (auto &i: g) i=i*n%p;
    return get_exp(g);
}

int n, m, a, b;
int fac[MAXN], ifac[MAXN];

poly get_f(int pr) {
    poly f(m);
    for (int i=0; i<m; ++i)
        f[i]=(p-pr*ifac[i]%p)%p;
    f[0]++;
    return get_inv(f);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin>>n>>m>>a>>b; m++;
    if (a==b) {
        for (int i=0; i<=m; ++i) cout<<1<<'\n';
        return 0;
    }
    fac[0]=ifac[0]=1;
    for (int i=1; i<=1e5; ++i) fac[i]=fac[i-1]*i%p, ifac[i]=inv(fac[i]);
    int pr=a*inv(b)%p, apr=(p+1-pr)%p;
    auto g=get_f(apr);  poly f(m);
    for (int i=0; i<m; ++i) f[i]=ifac[i];
    f=convolution(f,g);
    for (int i=0; i<m; ++i) {
        cout<<pr*f[i]%p*fac[i]%p<<'\n';
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 13ms
memory: 9680kb

input:

1 3 1 2

output:

1
2
6
26

result:

ok 4 lines

Test #2:

score: -100
Wrong Answer
time: 13ms
memory: 10084kb

input:

100 5 1 6

output:

1
6
66
1086
23826
653406

result:

wrong answer 2nd lines differ - expected: '600', found: '6'