QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#22032 | #2834. Nonsense | Qingyu | AC ✓ | 265ms | 105376kb | C++20 | 2.8kb | 2022-03-09 01:03:22 | 2022-04-30 00:42:03 |
Judging History
answer
#include <bits/stdc++.h>
const int mod = 998244353;
inline int inc(int x, int y) { x += y - mod; return x + (x >> 31 & mod); }
inline int dec(int x, int y) { x -= y; return x + (x >> 31 & mod); }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
inline void upd(int &x, int y) { x = inc(x, y); }
inline void dpu(int &x, int y) { x = dec(x, y); }
inline void pud(int &x, int y) { x = mul(x, y); }
inline int fastpow(int x, int p) {
int r = 1;
while (p) {
if (p & 1) r = mul(r, x);
x = mul(x, x);
p >>= 1;
}
return r;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int n, x, y, q;
const int lim = 2e5 + 50;
std::vector<int> inv(lim), fact(lim), factinv(lim);
fact[0] = 1;
for (int i = 1; i < lim; ++i)
fact[i] = mul(i, fact[i - 1]);
factinv[lim - 1] = fastpow(fact[lim - 1], mod - 2);
for (int i = lim - 2; i >= 0; --i) {
factinv[i] = mul(i + 1, factinv[i + 1]);
}
for (int i = 1; i < lim; ++i) {
assert(mul(fact[i], factinv[i]) == 1);
}
for (int i = 1; i < lim; ++i)
inv[i] = mul(factinv[i], fact[i - 1]);
auto comb = [&](int n, int m) {
if (n < m) return 0;
return mul(mul(fact[n], factinv[m]), factinv[n - m]);
};
while (std::cin >> n >> x >> y >> q) {
if (std::cin.eof()) break;
std::vector<int> a(q), b(q);
int mx = 0, prod = 1;
for (int i = 0; i < q; ++i) {
std::cin >> a[i] >> b[i];
}
mx = std::max(*std::max_element(a.begin(), a.end()), *std::max_element(b.begin(), b.end())) + 1;
std::vector<std::vector<int>> f(mx + 1, std::vector<int>(mx + 1));
std::vector<int> binom(2 * mx + 1);
// C(n + 1, i)
binom[0] = 1;
for (int i = 1; i <= 2 * mx; ++i) {
binom[i] = mul(binom[i - 1], mul(inv[i], n + 2 - i));
}
if (x == y) {
std::vector<int> power(lim);
power[0] = 1;
for (int i = 0; i < q; ++i) {
int z = binom[a[i] + b[i] + 1];
std::cout << mul(z, fastpow(x, n - a[i] - b[i])) << '\n';
}
}
else {
f[0][0] = fastpow(inc(x, y), n);
int d = fastpow(dec(x, y), mod - 2);
std::vector<int> pa(mx), pb(mx);
for (int i = 0; i < mx; ++i) {
pa[i] = fastpow(x, n + 1 - i);
pb[i] = fastpow(y, n + 1 - i);
}
f[0][0] = mul(d, dec(pa[0], pb[0]));
for (int i = 1; i < mx; ++i) {
int A = 0;
int B = mul(binom[i], pb[i]);
f[0][i] = dec(A, B);
A = mul(binom[i], pa[i]);
B = 0;
f[i][0] = dec(A, B);
}
for (int i = 1; i < mx; ++i) {
upd(f[0][i], f[0][i - 1]);
pud(f[0][i], d);
dpu(f[i][0], f[i - 1][0]);
pud(f[i][0], d);
}
for (int i = 1; i <= mx; ++i)
for (int j = 1; j <= mx; ++j) {
dpu(f[i][j], f[i - 1][j]);
upd(f[i][j], f[i][j - 1]);
pud(f[i][j], d);
}
for (int i = 0; i < q; ++i) {
std::cout << f[a[i]][b[i]] << '\n';
}
}
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5472kb
input:
3 1 2 2 1 1 1 2 100 2 3 1 1 1
output:
6 1 866021789
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 10ms
memory: 9528kb
input:
1000000000 0 1 1 1000 1000 2 0 0 1 1 1 2 998244352 998244352 1 1 1
output:
381781645 1 1
result:
ok 3 lines
Test #3:
score: 0
Accepted
time: 166ms
memory: 103728kb
input:
1000000000 998244351 998244352 1 5000 5000
output:
663228915
result:
ok single line: '663228915'
Test #4:
score: 0
Accepted
time: 55ms
memory: 6464kb
input:
105886041 9 3 200 4 3 5 1 1 1 4 1 3 3 1 5 2 1 1 5 2 1 1 5 3 3 4 4 2 1 4 4 1 2 5 2 5 2 2 5 4 5 3 3 4 3 1 4 3 1 5 4 5 3 5 2 5 3 3 3 1 3 4 3 2 3 3 5 1 3 3 5 2 3 4 4 3 4 5 5 2 3 1 1 3 3 4 2 1 4 4 5 2 3 1 5 2 2 4 2 5 5 2 1 4 3 3 3 3 1 2 1 2 5 1 1 4 4 1 5 1 5 3 1 3 2 2 2 4 1 5 5 3 4 2 2 2 1 5 3 5 3 2 2 1 ...
output:
721440251 764408668 442427888 914530150 115811774 360614503 666106268 360614503 666106268 360614503 115811774 166867820 666106268 166867820 985976063 717651702 717651702 405340273 435048189 115811774 721440251 719754512 660548079 998056822 165742634 717651702 165742634 115811774 407319461 721440251 ...
result:
ok 200000 lines
Test #5:
score: 0
Accepted
time: 30ms
memory: 6392kb
input:
405229773 25 79 200 3 3 5 5 5 5 1 5 2 4 2 4 3 1 3 3 5 4 1 5 2 1 3 1 4 1 2 5 1 4 4 4 4 1 5 5 5 3 2 2 1 1 2 1 4 2 4 4 2 3 5 1 4 3 2 3 3 4 4 3 2 2 3 3 1 4 5 3 2 2 3 1 1 1 3 3 3 5 1 3 5 2 1 1 1 4 5 5 5 5 4 1 2 5 2 5 1 4 1 1 3 3 5 4 1 2 1 1 2 5 4 3 5 4 3 3 5 2 3 3 4 1 2 3 2 5 1 3 4 3 4 4 4 2 5 1 2 5 3 5 ...
output:
52820293 692687559 692687559 899722361 150221007 150221007 570819646 52820293 9962865 899722361 594892845 570819646 90708097 161767707 25275214 680941576 90708097 692687559 142946866 827907378 868929596 594892845 73037078 680941576 897540013 658419918 202971687 897540013 38775730 202971687 827907378...
result:
ok 200000 lines
Test #6:
score: 0
Accepted
time: 39ms
memory: 5484kb
input:
205514256 631068448 638301474 200 2 5 2 4 1 4 1 5 4 2 1 5 4 2 1 2 5 4 3 2 3 5 4 3 2 4 4 5 3 2 5 5 1 1 3 2 3 2 5 2 4 2 4 3 4 2 3 5 2 4 5 1 2 1 2 3 3 1 5 1 3 1 1 3 2 5 5 4 4 5 2 1 5 4 5 1 2 3 5 3 5 2 1 2 2 2 5 2 2 4 1 1 3 1 1 3 4 4 2 3 1 2 2 4 1 1 1 5 3 5 2 2 2 2 1 5 2 5 5 2 2 5 3 1 1 3 5 1 5 3 2 3 3 ...
output:
372109930 532818312 880334055 931386950 851000884 931386950 851000884 920232088 545949965 457738522 874230202 29735043 532818312 831616270 457738522 744561645 232363848 457738522 457738522 18438814 851000884 29735043 851000884 874230202 532818312 870223579 812363425 209681041 864355959 870223579 864...
result:
ok 200000 lines
Test #7:
score: 0
Accepted
time: 44ms
memory: 5480kb
input:
371075301 713524167 984212326 2000 28 33 40 18 14 29 49 43 10 39 45 38 32 38 19 31 24 12 35 41 8 19 41 9 19 42 20 28 36 6 3 29 28 44 35 38 5 22 26 12 13 47 8 30 38 32 12 21 36 25 45 46 50 50 22 9 5 31 14 10 30 13 36 2 33 12 17 24 18 45 3 47 37 25 50 13 26 25 11 4 22 34 18 6 31 36 43 27 18 22 12 16 3...
output:
35509436 159833571 484242097 119046197 513595595 812038704 406494518 52232286 582008066 546786732 389948063 577535640 846537158 493495311 405937265 461091227 835518929 219508439 149463993 145136822 152212306 669088231 12828040 963047886 771023770 274264976 352767249 37662120 746104740 848752621 5766...
result:
ok 200000 lines
Test #8:
score: 0
Accepted
time: 62ms
memory: 6584kb
input:
326744271 690638130 696925215 20000 298 465 150 111 63 22 485 492 226 239 467 478 334 287 400 367 457 199 263 401 456 457 435 390 473 368 203 88 439 365 427 317 429 216 177 287 139 204 413 301 212 155 37 209 262 72 461 488 237 15 384 485 124 217 129 490 346 61 447 89 347 404 210 241 321 425 264 227 ...
output:
320182528 885037169 987260454 567004035 675906158 296063037 102545299 839780836 55989828 968396611 608553216 520690730 757453601 987339585 479505716 407039045 797684534 963385288 1943856 788131468 382178517 221019084 438142020 219895722 224755828 311507010 127291193 52822780 618671283 854120409 5053...
result:
ok 200000 lines
Test #9:
score: 0
Accepted
time: 231ms
memory: 105288kb
input:
436870970 392052048 645851299 200000 4938 818 1523 3467 973 4383 3788 2554 4471 1017 4676 1623 177 2249 3721 211 3492 3954 3252 4140 2971 4325 688 1381 3780 2479 1145 2483 3467 4343 2162 4705 3191 4416 2805 4917 4883 853 3824 4889 3910 4856 3082 2723 4156 921 1154 4685 226 1293 1120 237 2829 349 441...
output:
9544620 518912284 541614157 372073856 362578361 426236025 377863983 425477712 434770014 467638442 62493689 954484988 745559578 551774553 873609004 96439247 749859094 516502191 615526243 205247799 796287550 274795834 944667137 118164303 98105707 288964279 244923144 643945654 929130123 302481429 88253...
result:
ok 200000 lines
Test #10:
score: 0
Accepted
time: 240ms
memory: 105376kb
input:
175875716 410144900 97097634 200000 1711 72 299 4642 4961 1242 674 698 4214 1107 4622 1946 3094 4971 471 933 1245 2703 3733 2457 4650 886 1705 2898 2833 2599 1823 901 1842 3930 595 1814 88 4146 176 4450 3098 3442 4234 3374 3365 3044 1870 2238 3400 1539 1917 2798 3470 2091 2237 429 2768 4235 1039 837...
output:
180285591 728667493 109737898 720984986 279445479 180498901 783848532 604344419 536446846 224995985 665917962 929673586 208787825 531073777 806621604 473352896 279811957 709558012 901741246 903915284 782351989 864288830 807962018 309859544 896705274 116347208 156158893 632184733 808685122 308565845 ...
result:
ok 200000 lines
Test #11:
score: 0
Accepted
time: 241ms
memory: 105280kb
input:
859419071 629138239 126993191 200000 3981 463 837 1387 2908 3764 1344 4633 3278 2882 4600 2969 1962 137 15 55 2512 3969 3870 1166 3169 1093 800 1192 2522 1203 4317 1487 2598 3813 960 1840 4705 314 49 1347 1165 2293 1188 4 2465 1709 1993 2181 4757 4332 3794 3282 967 1657 3671 4523 3649 4262 2909 1165...
output:
867756937 422135696 915428024 787433162 129438614 977942587 262760809 699704848 218165309 156252640 271212750 871880284 905128694 132897747 963078461 328290579 894081009 486573486 626892225 253590588 54373830 621621839 25899231 740661396 831635457 350219485 202746694 363446530 42306428 72765588 6762...
result:
ok 200000 lines
Test #12:
score: 0
Accepted
time: 228ms
memory: 105304kb
input:
598423817 647231091 44265481 200000 3459 4716 4614 2562 1896 2920 2822 72 3021 676 4137 3292 4879 4756 4469 3073 265 2718 2456 3675 4040 4142 1008 413 2383 1323 4187 3009 2868 3400 4393 845 113 2748 124 2096 3572 2586 1599 3489 4623 4898 2268 2097 3593 3054 2260 4099 1914 3942 2492 2419 3587 852 223...
output:
791096233 178462366 141648872 918959026 235387354 847317505 843825690 9971812 744172110 649326488 392449327 158673420 659808836 921794689 625511457 481383673 478884995 6695377 830706196 107832629 701458719 814597110 658276482 670012724 271314136 124430361 198729895 355483258 804986985 37922226 99642...
result:
ok 200000 lines
Test #13:
score: 0
Accepted
time: 235ms
memory: 105292kb
input:
192204371 967313827 191766284 200000 2936 4778 4878 4546 884 2075 2005 3216 869 766 570 2807 2796 2478 2027 3795 4506 658 233 4288 3424 2999 1217 1930 1436 635 1354 2236 1243 1499 529 250 4713 3966 2495 4334 4491 2879 521 4270 1781 3087 3352 1612 2837 3672 4919 317 3262 3931 2120 3419 1629 2443 1151...
output:
282379762 255110320 568369113 208637836 91715322 496993246 833845378 443539517 576369315 165018943 690210396 485433774 145676324 966157682 468232499 717280774 89510141 219976903 214885574 383114869 343746454 298772564 719929421 613677811 230732800 612123621 817733005 686526412 338229708 473980891 72...
result:
ok 200000 lines
Test #14:
score: 0
Accepted
time: 252ms
memory: 105092kb
input:
931209116 289152210 339267087 200000 2414 1327 3655 721 4872 3935 1187 3655 613 857 107 3130 2610 2097 1482 1814 4155 2111 715 1797 103 4560 2233 1152 4001 756 1224 654 4217 1086 3961 62 121 1399 274 1571 4193 3980 3636 859 1236 2083 4435 720 2081 1586 2578 1135 18 4320 3644 4019 1568 1330 2772 2922...
output:
844307260 443661987 375183620 124021238 801293954 147207268 439051822 858224855 181810697 713309471 345525147 58193678 860288759 183544438 756853384 711878600 366391096 853795832 142325545 420328734 816066001 333877562 495706902 7555389 714692701 651788433 395511144 992425771 357059675 105457951 217...
result:
ok 200000 lines
Test #15:
score: 0
Accepted
time: 254ms
memory: 105360kb
input:
935055078 609234946 486767891 200000 3788 581 2432 408 1564 3090 369 1799 356 3651 1541 2645 527 4819 1336 4832 4203 860 4301 4307 4486 1121 145 373 1158 2364 1094 4880 295 673 98 2171 2017 1129 2645 3809 4304 4272 4046 1640 3394 272 3223 235 917 2204 1045 4249 4070 4309 4761 4211 3802 2921 4393 107...
output:
827268417 488412806 156864510 234209553 600454885 622031861 433517368 322539114 643044201 479878252 790248245 670307759 823038517 106845259 490980255 710789898 265216733 303289089 49384408 631647611 839000701 849222238 356706941 510423522 845130291 485410691 594123084 711149423 268649614 428756332 7...
result:
ok 200000 lines
Test #16:
score: 0
Accepted
time: 234ms
memory: 105192kb
input:
528835632 627327798 634268694 200000 3265 642 2697 4688 2848 2246 4551 4535 100 1037 1078 2968 3444 4437 790 554 1148 4608 2079 2624 1165 4978 3057 1890 2915 188 964 4106 2862 668 826 1176 130 859 2720 1047 2519 3077 2969 125 2041 4269 4307 4343 160 3630 999 2362 2314 4699 2093 4403 1037 4512 2910 1...
output:
282849035 339868804 439122742 422331208 253830709 236239323 273429778 703276409 192263399 17757910 645722648 766282359 916219254 203412052 910943291 566162741 52662427 400927060 744194766 94615021 974568793 6461715 657134975 258857026 448413351 285785539 766473691 910000099 120023891 539522265 49261...
result:
ok 200000 lines
Test #17:
score: 0
Accepted
time: 265ms
memory: 105280kb
input:
267840377 947410534 551540983 200000 447 4896 1474 3567 4540 4105 3734 782 2139 1935 215 2483 1361 2160 1052 1276 1197 2549 2152 2837 4740 3835 3266 1111 2776 4501 3131 4820 3940 1063 1962 989 4730 3293 2795 3284 2629 3370 3379 1714 1495 2457 2286 1154 4404 1544 2170 476 1365 4688 913 2299 975 2590 ...
output:
123313334 933796559 241675810 204150508 236363652 278947568 89412138 698739296 559851004 385273726 681423583 45926821 844104100 523155595 228782713 132582995 772616450 924000898 518924970 122737539 539006829 270233102 306257287 158602839 950515800 275256965 687957777 143941024 862576015 894449347 40...
result:
ok 200000 lines
Test #18:
score: 0
Accepted
time: 264ms
memory: 105152kb
input:
861620931 269248917 699041787 200000 4924 2661 2546 550 3528 3261 2916 3926 2691 4730 4752 2806 4278 4882 2803 1998 438 4001 738 347 1420 396 4282 2628 4933 1109 3001 1750 1915 650 395 394 2434 3022 166 3226 36 1767 2302 2495 3654 646 3370 2966 3240 2162 2125 3590 3121 1973 542 195 3209 4181 1152 28...
output:
673477646 167372996 923615488 227417271 845305746 986413222 591141348 516204018 55507233 740996504 649865339 450187141 759416023 660719017 67181244 667284369 940752116 147724773 709110797 808227949 408434865 821601168 706009731 661237954 58233624 10316900 571192907 578830380 778250341 305686949 6749...
result:
ok 200000 lines