QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#402518#6811. Alice's DollsStarrykiller#WA 13ms12352kbC++233.9kb2024-04-30 19:05:162024-04-30 19:05:16

Judging History

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

  • [2024-04-30 19:05:16]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:12352kb
  • [2024-04-30 19:05:16]
  • 提交

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(poly a, int n, int deg) {
    poly res(deg); res[0]=1;
    while (n) {
        if (n&1) res=convolution(res,a);
        a=convolution(a,a);
        res.resize(deg);
        a.resize(deg); 
        n>>=1;
    }
    return res;
}

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]++;
    poly g(m);
    for (int i=0,pw=1; i<m; ++i) {
        g[i]=pw*ifac[i]%p;
        pw=pw*n%p;
    }
    f=qpow(get_inv(f),n+1,m);
    f=convolution(f,g);
    return f;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin>>n>>m>>a>>b; m++; n--;
    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);
    int pw=qpow(pr,n+1);
    for (auto &i: f) i=i*pw%p;
    for (int i=0; i<m; ++i) {
        cout<<f[i]*fac[i]%p<<'\n';
    }
}

详细

Test #1:

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

input:

1 3 1 2

output:

1
2
6
26

result:

ok 4 lines

Test #2:

score: 0
Accepted
time: 8ms
memory: 8692kb

input:

100 5 1 6

output:

1
600
363000
221433000
425510992
941092730

result:

ok 6 lines

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 5824kb

input:

82346 94247 998244352 998244352

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

wrong answer 2nd lines differ - expected: '82346', found: '1'