QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#301383#4922. 生活在对角线下zyc07041930 65ms52376kbC++144.2kb2024-01-09 19:03:402024-01-09 19:03:40

Judging History

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

  • [2024-01-09 19:03:40]
  • 评测
  • 测评结果:30
  • 用时:65ms
  • 内存:52376kb
  • [2024-01-09 19:03:40]
  • 提交

answer

#include <bits/stdc++.h>
#define PII pair<int, int>
using namespace std;
const int N = 1e5 + 3;
const int W = (N << 1);
const int M = 2e5 + 3;
const int mod = 998244353;
const int inv2 = 499122177;

inline int read() {
    char ch = getchar(); int x = 0, f = 1;
    while (!isdigit(ch)) {if (ch == '-') {f = -1;} ch = getchar();}
    while (isdigit(ch)) {x = (x << 3) + (x << 1) + ch - 48; ch = getchar();}
    return x * f;
}
int fac[W], inv[W];
inline int add(int x, int y) {x += y; return x >= mod ? x - mod : x;}
inline int del(int x, int y) {x -= y; return x < 0 ? x + mod : x;}
inline void Add(int &x, int y) {x = add(x, y);}
inline void Del(int &x, int y) {x = del(x, y);}
inline int qpow(int x, int y) {
    int res = 1;
    while (y) {
        if (y & 1) res = 1ll * res * x % mod;
        x = 1ll * x * x % mod;
        y >>= 1;
    }
    return res;
}
inline int C(int x, int y) {return (x < 0 || y < 0 || x < y) ? 0 : 1ll * fac[x] * inv[y] % mod * inv[x - y] % mod;}
struct NTT {
    int len;
    vector<int> f, g;
    
    void init(int n) {
        len = 1;
        while (len <= n + n) len <<= 1;
        f.clear(); g.clear();
        f.resize(len + 5); g.resize(len + 5);
    }
};

int T, c, p, q, L, cnt, pos[10][10], pw[N][10];
PII id[10];

inline int calc(int x, int y, int k) {return 1ll * pw[x][id[k].first] * pw[y][id[k].second] % mod;}

namespace subtask1 {
    const int N1 = 1005;

    int f[N1][N1], g[N1][N1][10];
    
    bool check() {return L <= 1000;}

    void solve() {
        f[0][0] = 1;
        for (int i = 0; i < cnt; ++i) g[0][0][i] = calc(0, 0, i);
        for (int i = 0; i <= L; ++i)
            for (int j = 0; j <= L; ++j) {
                if (i == 0 && j == 0) continue;
                if (i) Add(f[i][j], f[i - 1][j]);
                if (j) Add(f[i][j], f[i][j - 1]);
                for (int k = 0; k < cnt; ++k) {
                    if (i) Add(g[i][j][k], g[i - 1][j][k]);
                    if (j) Add(g[i][j][k], g[i][j - 1][k]);
                    if (j <= i) Add(g[i][j][k], 1ll * f[i][j] * calc(i, j, k) % mod);
                }
            }
        int n, m, ans;
        while (T--) {
            n = read(); m = read(); ans = 0;
            for (int i = 0; i < cnt; ++i) Add(ans, 1ll * g[n][m][i] * read() % mod);
            printf("%d\n", ans);
        }
    }
}

namespace subtask2 {
    int f[N], g[N], n, m, v, ans;

    bool check() {return T == 1 && p == 0 && q == 0;}

    void solve() {
        n = read(); m = read(); v = read();
        if (n == m) {
            g[n] = qpow(4, n);
			f[n] = 1ll * del(1ll * (n + m + 1) * C(n + m, n) % mod, g[n]) * inv2 % mod;
            printf("%lld\n", 1ll * add(f[n], g[n]) * v % mod);
        }else if (n < m) {
			g[0] = 1;
			for (int i = 1; i <= n; ++i) g[i] = 4ll * g[i - 1] % mod;
			for (int i = 0; i <= n; ++i) {
				f[i] = 1ll * del(1ll * (i + i + 1) * C(i + i, i) % mod, g[i]) * inv2 % mod;
				Add(ans, 1ll * add(f[i], g[i]) * del(C(n - i + m - i - 1, n - i), C(n - i + m - i - 1, n - i - 1)) % mod);
			}
			ans = 1ll * ans * v % mod;
			printf("%d\n", ans);
        }else {
			g[0] = 1; ans = 1ll * (n + m + 1) * C(n + m, n) % mod;
			for (int i = 1; i <= m; ++i) g[i] = 4ll * g[i - 1] % mod;
			for (int i = 0; i <= m; ++i) {
				f[i] = 1ll * del(1ll * (i + i + 1) * C(i + i, i) % mod, g[i]) * inv2 % mod;
				Del(ans, 1ll * f[i] * del(C(n - i - 1 + m - i, m - i), C(n - i - 1 + m - i, n - i)) % mod);
			}
			ans = 1ll * ans * v % mod;
			printf("%d\n", ans);
		}
    }
}

int main() {
    fac[0] = 1;
    for (int i = 1; i <= M; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
    inv[M] = qpow(fac[M], mod - 2);
    for (int i = M; i >= 1; --i) inv[i - 1] = 1ll * inv[i] * i % mod;
    T = read(); c = read(); p = read(); q = read(); L = read(); L = max(L, L + c);
    for (int i = 0; i <= p; ++i)
        for (int j = 0; j <= q; ++j)
            id[pos[i][j] = cnt++] = make_pair(i, j);
    for (int i = 0; i <= L; ++i) {
        pw[i][0] = 1;
        for (int j = 1; j <= max(p, q); ++j) pw[i][j] = 1ll * pw[i][j - 1] * i % mod;
    }

    // subtask2 :: solve(); exit(0);

    if (subtask1 :: check()) subtask1 :: solve();
    else if (subtask2 :: check()) subtask2 :: solve();
    return 0;
}

詳細信息

Subtask #1:

score: 1
Accepted

Test #1:

score: 1
Accepted
time: 23ms
memory: 50400kb

input:

1 -10 1 2 1000
825 815
107973512 400177523 812303207
164088430 603506669 337780072

output:

360076089

result:

ok 1 number(s): "360076089"

Test #2:

score: 0
Accepted
time: 22ms
memory: 51048kb

input:

1 424 1 4 576
130 554
926445673 393820912 634481616 292175028 733650737
100427548 899689095 876811717 849191704 696040532

output:

564712546

result:

ok 1 number(s): "564712546"

Test #3:

score: 0
Accepted
time: 28ms
memory: 50464kb

input:

1 -171 2 1 1000
805 634
250066876 719653007
284194184 531322789
491311782 185842441

output:

910556244

result:

ok 1 number(s): "910556244"

Test #4:

score: 0
Accepted
time: 25ms
memory: 52376kb

input:

1 11 4 1 989
142 153
581558550 138798754
575233123 788754497
582314564 303591688
635874631 658261955
615116681 498307457

output:

918405181

result:

ok 1 number(s): "918405181"

Test #5:

score: 0
Accepted
time: 22ms
memory: 51032kb

input:

1 -87 1 2 1000
164 77
264180617 338145439 610918500
800846696 216126209 112962819

output:

629819261

result:

ok 1 number(s): "629819261"

Subtask #2:

score: 9
Accepted

Dependency #1:

100%
Accepted

Test #6:

score: 9
Accepted
time: 43ms
memory: 50856kb

input:

100000 -99 2 1 1000
712 613
238230707 820405654
473765646 826816733
751513618 421153458
209 110
22075351 398854663
148159396 487281124
972932017 200517786
383 284
22252771 205525630
491328752 607545155
561318911 135661425
929 830
156478040 89922795
380802607 32081978
898588032 110586958
956 857
4206...

output:

863094157
570366074
281608243
247495628
396961441
855444791
694374848
782506902
280202079
688077364
610676536
115373962
360154110
834242083
887647721
164293717
759683961
710870451
213441970
863772654
514218158
532711794
558875294
421795761
517787006
458381459
506983637
742686106
435175768
111255264
...

result:

ok 100000 numbers

Test #7:

score: 0
Accepted
time: 55ms
memory: 50400kb

input:

100000 252 3 1 748
130 382
311369319 709099006
49474431 724072531
761415026 251406187
389170658 169808960
581 833
89779535 938252574
504798466 677842435
654289171 763708659
719082912 762770851
691 943
571693157 187035992
300995260 403041189
726726538 63983502
814000657 315732021
121 373
339102104 42...

output:

516270157
614211606
655396807
981733406
752565578
312973289
850750616
826813023
753739511
227580123
199177890
403714939
559334967
370464926
363937285
583678656
239132195
834163477
111915553
68813179
875627540
299872127
660063389
31474925
464946255
125818391
645016505
267670615
440441568
356463850
84...

result:

ok 100000 numbers

Test #8:

score: 0
Accepted
time: 65ms
memory: 50980kb

input:

100000 195 2 2 805
325 520
266481322 663615421 428019284
968378746 158386978 211891009
161987045 142931644 790431809
621 816
756898302 952132541 196745128
424307295 926376261 130425563
604844618 645296808 252920984
60 255
873310227 887037637 787608776
98214115 355810775 242821836
537250851 650821017...

output:

922269244
757786754
400099571
332972619
780501723
469958234
540206804
924583388
519189002
566620024
244468115
73221163
663221021
159111716
451144022
658783977
656844692
831466434
186871631
60740257
542611012
773315130
755261907
193772041
628947709
363111530
452621670
349808610
264947076
342250907
16...

result:

ok 100000 numbers

Subtask #3:

score: 20
Accepted

Test #9:

score: 20
Accepted
time: 0ms
memory: 11712kb

input:

1 4683 0 0 95317
86560 91243
412303217

output:

952052072

result:

ok 1 number(s): "952052072"

Test #10:

score: 0
Accepted
time: 5ms
memory: 10272kb

input:

1 -24796 0 0 100000
93338 68542
849332154

output:

980840409

result:

ok 1 number(s): "980840409"

Test #11:

score: 0
Accepted
time: 5ms
memory: 11640kb

input:

1 40156 0 0 59844
39551 79707
566086447

output:

620552907

result:

ok 1 number(s): "620552907"

Test #12:

score: 0
Accepted
time: 5ms
memory: 11324kb

input:

1 -714 0 0 100000
72672 71958
817542139

output:

799272798

result:

ok 1 number(s): "799272798"

Test #13:

score: 0
Accepted
time: 0ms
memory: 9420kb

input:

1 23418 0 0 76582
6862 30280
442920403

output:

642352133

result:

ok 1 number(s): "642352133"

Test #14:

score: 0
Accepted
time: 5ms
memory: 12052kb

input:

1 42983 0 0 57017
42753 85736
380012689

output:

828068267

result:

ok 1 number(s): "828068267"

Test #15:

score: 0
Accepted
time: 0ms
memory: 9800kb

input:

1 -25448 0 0 100000
47466 22018
617788426

output:

485886943

result:

ok 1 number(s): "485886943"

Test #16:

score: 0
Accepted
time: 2ms
memory: 10696kb

input:

1 -35138 0 0 100000
49912 14774
472000456

output:

323681794

result:

ok 1 number(s): "323681794"

Test #17:

score: 0
Accepted
time: 0ms
memory: 11572kb

input:

1 15928 0 0 84072
57657 73585
31014982

output:

184096139

result:

ok 1 number(s): "184096139"

Test #18:

score: 0
Accepted
time: 4ms
memory: 12080kb

input:

1 5316 0 0 94684
36186 41502
601085246

output:

51887433

result:

ok 1 number(s): "51887433"

Subtask #4:

score: 0
Wrong Answer

Dependency #3:

100%
Accepted

Test #19:

score: 0
Wrong Answer
time: 4ms
memory: 10464kb

input:

100000 43925 0 0 56075
36770 80695
880793638
55133 99058
946571985
27169 71094
601132030
42027 85952
954509221
1261 45186
326012305
12030 55955
997023025
9914 53839
788665071
39921 83846
193760311
25774 69699
584278712
28428 72353
45133606
32564 76489
40466335
35483 79408
491164633
1587 45512
842380...

output:


result:

wrong answer Answer contains longer sequence [length = 100000], but output contains 0 elements

Subtask #5:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Dependency #3:

100%
Accepted

Test #26:

score: 0
Wrong Answer
time: 4ms
memory: 10736kb

input:

1 -40679 1 3 100000
75191 34512
321693501 896183087 224533692 282076683
38691763 630172019 273852722 127891101

output:


result:

wrong answer Answer contains longer sequence [length = 1], but output contains 0 elements

Subtask #6:

score: 0
Wrong Answer

Test #41:

score: 0
Wrong Answer
time: 0ms
memory: 9848kb

input:

100000 0 2 1 100000
48964 48964
666670967 90494987
74847122 615108201
29533064 582540229
14418 14418
391779909 223696706
701170191 885097597
551643398 25626747
81584 81584
951326734 520293397
13860946 896899117
821166399 282263457
76849 76849
598606953 879771697
930252135 671750715
673503431 3060699...

output:


result:

wrong answer Answer contains longer sequence [length = 100000], but output contains 0 elements

Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

0%