QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#301383 | #4922. 生活在对角线下 | zyc070419 | 30 | 65ms | 52376kb | C++14 | 4.2kb | 2024-01-09 19:03:40 | 2024-01-09 19:03:40 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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%