QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#610337#6811. Alice's DollstosaniaAC ✓264ms139688kbC++148.7kb2024-10-04 15:38:372024-10-04 15:38:38

Judging History

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

  • [2024-10-04 15:38:38]
  • 评测
  • 测评结果:AC
  • 用时:264ms
  • 内存:139688kb
  • [2024-10-04 15:38:37]
  • 提交

answer

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

const int N = 800007;
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][20][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(19);//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;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 108076kb

input:

1 3 1 2

output:

1
2
6
26

result:

ok 4 lines

Test #2:

score: 0
Accepted
time: 7ms
memory: 106028kb

input:

100 5 1 6

output:

1
600
363000
221433000
425510992
941092730

result:

ok 6 lines

Test #3:

score: 0
Accepted
time: 217ms
memory: 129712kb

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: 244ms
memory: 139688kb

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: 7ms
memory: 106092kb

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: 249ms
memory: 137760kb

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: 264ms
memory: 135592kb

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: 148ms
memory: 122348kb

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: 60ms
memory: 122612kb

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: 141ms
memory: 135428kb

input:

100000 0 123456789 234567890

output:

1

result:

ok single line: '1'