QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#383270 | #5547. Short Function | kevinyang# | AC ✓ | 37ms | 5544kb | C++17 | 1.2kb | 2024-04-09 08:52:16 | 2024-04-09 08:52:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int modpow(int x, int y) {
return !y?1:((y % 2 ? x : 1) * modpow((x * x) % mod, y / 2)) % mod;
}
/*
ax + b
cx + d
acx^2
*/
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
int n,k;
cin >> n >> k;
vector<int>a(n+1);
for(int i = 1; i<=n; i++){
cin >> a[i];
}
int q = 0; int r = 2;
int aq = 0; int ar = 1;
for(int i = 0; i<30; i++){
if(k & 1<<i){
int nq = aq*q%(mod-1)*n + r*aq + ar * q;
int nr = r*ar;
nq += nr/n;
nq%=mod-1;
nr%=n;
aq = nq;
ar = nr;
}
int nq = q*q%(mod-1)*n + 2*r*q;
int nr = r*r;
nq += nr/n;
nr%=n;
q = nq;
r = nr;
q%=(mod-1);
}
int tot = 1;
for(int i = 1; i<=n; i++){
tot*=a[i];
tot%=mod;
}
int extra = modpow(tot,aq);
vector<int>psa(2*n+1);
psa[0] = 1;
for(int i = 1; i<=n; i++){
psa[i] = psa[i+n] = a[i];
}
for(int i = 1; i<=2*n; i++){
psa[i]*=psa[i-1];
psa[i]%=mod;
}
for(int i = ar; i<n+ar; i++){
int v = psa[i] * modpow(psa[i-ar],mod-2)%mod;
cout << v*extra%mod;
if(i+1<n+ar)cout << ' ';
}
cout << '\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3592kb
input:
5 2 1 2 3 4 5
output:
24 120 60 40 30
result:
ok 5 number(s): "24 120 60 40 30"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
8 3 12 5 16 14 10 6 9 2
output:
14515200 14515200 14515200 14515200 14515200 14515200 14515200 14515200
result:
ok 8 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
6 10 3 7 8 2 9 5
output:
56347321 169041963 833775940 811788154 844769833 639990479
result:
ok 6 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
2 100 1 2
output:
917380677 917380677
result:
ok 2 number(s): "917380677 917380677"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
119 1000000000 179906895 883175111 831258723 617910763 41850684 952649819 667608052 992898634 871657688 261948841 858714230 452797779 698675390 39373823 268148685 762575950 789163136 676908074 134428624 583625412 549545785 415007638 564283552 596519552 575204092 884934270 632550339 21505752 66058955...
output:
375116230 26429781 713091228 558890530 21930790 178825460 670077410 523152589 669414287 97987884 399677029 513881456 107722471 353957452 946672010 508449163 23021836 445766752 334151026 1826665 117696761 694568123 949667235 876304874 367174487 169501255 197879871 462516615 208040656 770105543 958714...
result:
ok 119 numbers
Test #7:
score: 0
Accepted
time: 14ms
memory: 4752kb
input:
60928 1000000000 647034012 758455477 62531806 937429685 597725392 151383361 375173809 62379754 462035375 121434573 370644921 339070881 459180118 524525232 539383343 825690592 862037426 643159998 695754897 799399539 500951305 271294315 721183291 342758823 636098292 891075586 970208329 452034355 24183...
output:
946516222 315310335 562683949 614527727 961228460 778673772 124575531 202861813 358534859 463200249 437273635 356795795 655879659 656235247 146099590 498035900 865525574 430376201 130782952 913561838 202654508 797237275 262113868 612420852 524859489 566612380 301295588 835552939 554799099 203338329 ...
result:
ok 60928 numbers
Test #8:
score: 0
Accepted
time: 34ms
memory: 5544kb
input:
100000 1000000000 984343843 231975068 819209000 195274035 278601046 224249013 804551337 222857445 609670477 952095628 931244133 748912217 393911483 638420373 194474592 489497425 54112292 382356337 859661508 879670192 828408437 52769079 102069187 265385606 611233228 110980823 246539650 225276298 8149...
output:
745607263 778449814 353873669 967019424 244678385 67448965 975575340 35825155 543051000 897593204 666370492 160911161 881003284 379638077 472463432 733502290 952977171 566586173 738710333 440820311 746325822 781552527 811842350 367482145 969630877 540289575 631912195 989032516 843221796 756415366 61...
result:
ok 100000 numbers
Test #9:
score: 0
Accepted
time: 33ms
memory: 5408kb
input:
100000 536870911 992923113 670377734 358643360 204598419 870214427 589880933 100598747 740363182 956718521 558499933 169035359 450915543 368574733 451719664 818479228 206798116 581171738 364002822 917110169 28508603 166986560 105980102 551535856 58737284 297671188 233046177 112082256 567791130 29734...
output:
995235167 629406687 342518242 677174492 860271899 341054397 898158891 46524885 180769937 240457073 464512693 16768467 193870169 314392458 802152668 925240470 466722744 427195520 466234573 953661603 366988993 365489746 630020963 732705556 833607561 481605378 898457610 170423826 861275866 123476267 34...
result:
ok 100000 numbers
Test #10:
score: 0
Accepted
time: 33ms
memory: 5420kb
input:
100000 536870912 754800614 502825948 950091792 122161118 428395966 55774196 78794559 832947844 159667506 476030916 40726151 873328273 321207504 769562590 625129960 319641119 397621703 618984815 919101953 748926051 338473807 54440461 574923741 953948209 463696988 589932101 230349092 98546578 87295555...
output:
675478200 532380810 333384354 651969929 87674770 802932048 530760793 845053441 295784675 515945054 268042632 360570667 37787857 305887820 637674540 108516569 11944905 533018219 942086643 988234164 20218516 47356547 553152095 54920589 416122761 741700692 762929703 795958059 278571227 348057648 513276...
result:
ok 100000 numbers
Test #11:
score: 0
Accepted
time: 25ms
memory: 5404kb
input:
100000 1000000000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 100000 numbers
Test #12:
score: 0
Accepted
time: 32ms
memory: 5400kb
input:
100000 1000000000 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 99...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 100000 numbers
Test #13:
score: 0
Accepted
time: 3ms
memory: 3676kb
input:
15883 711828783 312783530 785974617 472786567 438402384 714817844 634994013 511592804 801103447 886097329 950860104 523448114 900891739 713995253 178577344 894077606 344034853 917396601 357201139 210483471 268951796 264707617 751484456 784102044 475778641 449351682 453603143 602571932 951751801 9133...
output:
402898339 339110117 136011220 688608547 190365859 739078915 721358903 437751504 533379374 214457350 833448838 662958039 465760972 344869361 581709073 149594046 53934609 389375119 941383148 524211284 280310048 659611233 936028933 165092445 645217798 9103063 440921672 717226110 284293133 795282593 754...
result:
ok 15883 numbers
Test #14:
score: 0
Accepted
time: 22ms
memory: 4612kb
input:
65535 33224114 122966631 711823623 297426182 8495263 825482104 39399772 90566442 903771191 553698247 634019407 729484984 349621957 428163505 902066309 283495328 684440700 903057765 995198686 905578252 849330088 384341154 775567846 678333451 230898212 690565047 714584134 164580605 836255376 838388549...
output:
715872357 963116423 639947711 226834435 599447728 959448236 751871241 354868050 496392542 100775142 509944414 63492978 348952962 941136966 63579858 871177797 836444927 458025431 84061656 39284755 472879410 318873513 358463179 844539675 40654131 916284668 512600028 751361426 248934886 634157613 18434...
result:
ok 65535 numbers
Test #15:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
1 1 998244352
output:
1
result:
ok 1 number(s): "1"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
1 1000000000 998244352
output:
1
result:
ok 1 number(s): "1"
Test #17:
score: 0
Accepted
time: 34ms
memory: 5400kb
input:
100000 100000 547849979 591803790 713933745 842783511 601705131 856439370 543926555 845764262 422911009 644760153 383706870 436818961 297012240 890207363 56613408 961970912 382768333 476826500 790335043 527966369 479134501 567047278 392095202 923971612 834610909 70911345 336803813 86976329 647033915...
output:
956304162 166332847 652523025 266396102 292344991 948225826 993000177 677534377 657536601 591720636 273282300 184186490 66504696 274846815 601264826 631486634 907793548 147248294 330139758 951392889 105697877 128004776 132552618 749695425 552838251 137414299 550671281 251727200 68604958 297805594 26...
result:
ok 100000 numbers
Test #18:
score: 0
Accepted
time: 37ms
memory: 5408kb
input:
100000 99999 841866692 314060913 259638941 714178319 513605874 141986007 953833732 245144403 423956567 564203114 582624297 780589424 387602898 948646246 223318201 630750743 942982749 125177378 434615549 572329667 111148206 315741581 547201413 144385372 32472022 192543977 331579635 708579564 77992538...
output:
261670676 459915967 402197633 13537114 577650279 191765208 314559716 503595454 748040395 883757134 336086864 323533496 547374724 656042686 43024524 112771507 172274101 243200250 150862833 496234591 867605152 424819327 214426612 363641186 520816546 576810994 370546732 764816004 140567862 484302409 49...
result:
ok 100000 numbers
Test #19:
score: 0
Accepted
time: 34ms
memory: 5472kb
input:
100000 1 95426071 339242652 30536117 908525604 741349299 832097717 65273046 539974739 279982386 170931733 954980428 251098198 7521098 401441877 334910609 992826930 202508588 215811492 597872789 366248380 148999276 778956469 860673250 148148959 26658942 234290381 346315354 529626192 673897011 8898872...
output:
199524908 314881968 443608160 718335632 778946149 687532507 980885595 326433883 752421759 167352927 390050650 584336589 815847617 362462293 598188425 852840041 698069617 323830556 452799170 915629426 613585969 15645303 501304156 617358058 617552848 78688753 215178423 911648393 342760378 347677754 21...
result:
ok 100000 numbers
Test #20:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
7 438546120 37582320 742047949 749603065 45749882 353575347 896156348 947428143
output:
609352595 531369837 959169129 421355534 776276808 865049314 181293713
result:
ok 7 numbers
Test #21:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
17 138470761 392746674 582407247 115409370 787445374 959354178 289272509 662710604 227483991 317973620 402326125 575228496 679052989 468291017 129760735 704157486 601893320 724503789
output:
909074001 148254642 104590006 301543255 546358321 146223964 779474500 506545153 19199434 197541688 382113133 228989886 301390969 361657078 943618894 948665558 57662042
result:
ok 17 numbers
Test #22:
score: 0
Accepted
time: 22ms
memory: 4684kb
input:
65536 8932229 481415362 603810503 21143150 44656288 602451759 544329721 582935364 420268446 777689072 20071478 883990423 719658408 480898826 810081829 711343834 482744166 849884482 718837757 520813828 319494910 175176429 818788531 160101252 885070860 852467699 485805373 86822013 385056557 382543604 ...
output:
501055311 501055311 501055311 501055311 501055311 501055311 501055311 501055311 501055311 501055311 501055311 501055311 501055311 501055311 501055311 501055311 501055311 501055311 501055311 501055311 501055311 501055311 501055311 501055311 501055311 501055311 501055311 501055311 501055311 501055311 ...
result:
ok 65536 numbers