QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#402521#6811. Alice's DollsStarrykiller#AC ✓1348ms28876kbC++233.9kb2024-04-30 19:10:402024-04-30 19:10:40

Judging History

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

  • [2024-04-30 19:10:40]
  • 评测
  • 测评结果:AC
  • 用时:1348ms
  • 内存:28876kb
  • [2024-04-30 19:10:40]
  • 提交

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';
    }
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

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

input:

1 3 1 2

output:

1
2
6
26

result:

ok 4 lines

Test #2:

score: 0
Accepted
time: 6ms
memory: 10724kb

input:

100 5 1 6

output:

1
600
363000
221433000
425510992
941092730

result:

ok 6 lines

Test #3:

score: 0
Accepted
time: 1174ms
memory: 28876kb

input:

82346 94247 998244352 998244352

output:

1
82346
791397598
40508009
538125741
435438716
697592329
964874802
317657163
799962739
585095577
16686097
449113834
769228973
331835396
374844347
218958949
104110468
158094364
333890471
898754640
11498373
509376414
878962890
373081322
784577837
472039442
921273818
635966440
395465507
275355856
33108...

result:

ok 94248 lines

Test #4:

score: 0
Accepted
time: 1348ms
memory: 27480kb

input:

99999 99998 1 1

output:

1
99999
17356471
681058015
897702913
273664856
341242002
872239399
469072873
314324010
366733079
438370760
733355951
836839610
300048400
309433479
458256580
792718955
518709315
637964452
7124024
647052287
379174959
801465042
656610000
821071425
723394325
932065530
543939213
40810170
153274766
279529...

result:

ok 99999 lines

Test #5:

score: 0
Accepted
time: 14ms
memory: 9820kb

input:

234 459 8713247 74362439

output:

1
550308667
652601851
21862568
312504180
301781771
955945774
241922434
687893799
220084008
951866075
223169979
261547613
851721240
108461996
645670062
647827677
740281647
567424949
65300355
783187507
824238091
706909540
715519504
74795499
263740113
795953643
525222901
990470578
720139891
531988015
3...

result:

ok 460 lines

Test #6:

score: 0
Accepted
time: 1125ms
memory: 27336kb

input:

100000 100000 34457 34458

output:

1
110072884
866073590
736351474
206840805
363851986
895119597
144145068
753578218
113903056
711499733
430574479
231258052
694514889
284319691
530696819
535538312
933991851
868518537
888564382
239789947
182502325
355499336
74503434
691778894
327131524
233789093
41501704
639617307
916312185
394659685
...

result:

ok 100001 lines

Test #7:

score: 0
Accepted
time: 1138ms
memory: 25244kb

input:

100000 100000 998244351 998244352

output:

1
50000
503486294
85094752
335515298
331724101
676123256
80958981
314512322
659052656
12751483
516505166
655297143
652329290
347750398
78055519
290808848
35067066
791903803
995363140
517288436
394436580
430863665
823972579
523698332
746439583
27677016
323067719
660639896
110677907
568717926
25289325...

result:

ok 100001 lines

Test #8:

score: 0
Accepted
time: 13ms
memory: 12676kb

input:

93248 34 1 499122177

output:

1
46624
177285358
111979882
696375359
818605358
237802954
608377035
863173334
196258366
607718397
364819065
360314917
233450239
952902294
131353496
959526592
687802720
477763385
488883348
507982668
818592811
76520370
194416851
590074140
13328434
672264252
42015845
921175397
849890303
603093773
61302...

result:

ok 35 lines

Test #9:

score: 0
Accepted
time: 614ms
memory: 25428kb

input:

53 99997 2394 7681238

output:

1
955048736
470514326
41111193
709347504
116606594
22612570
620495230
589459109
278168830
277523111
890862369
212779039
908656172
927315643
325078855
630813446
435720817
357034897
545024798
456613789
312453851
69393505
463880280
934933770
586168348
444543516
547460238
575392663
993322173
625521110
7...

result:

ok 99998 lines

Test #10:

score: 0
Accepted
time: 9ms
memory: 10404kb

input:

100000 0 123456789 234567890

output:

1

result:

ok single line: '1'