QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#108890 | #4476. 氪金手游 | myee | 100 ✓ | 124ms | 26960kb | C++11 | 5.2kb | 2023-05-26 21:10:38 | 2023-05-26 21:10:40 |
Judging History
answer
// 搁这儿搬 CTS2019 的题还是太毒瘤了些吧(虽然上课讲过了)。
// 思路:容斥。
// 过于牛逼。
#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
T ans=1%mod;
while(index)
{
if(index&1)ans=ans*base%mod;
base=base*base%mod,index>>=1;
}
return ans;
}
namespace ConstMod
{
template<const ullt p>
class mod_ullt
{
private:
ullt v;
inline ullt chg(ullt w){return(w<p)?w:w-p;}
inline mod_ullt _chg(ullt w){mod_ullt ans;ans.v=(w<p)?w:w-p;return ans;}
public:
mod_ullt():v(0){}
mod_ullt(ullt v):v(v%p){}
bol empty(){return!v;}
inline ullt val(){return v;}
friend bol operator<(mod_ullt a,mod_ullt b){return a.v<b.v;}
friend bol operator>(mod_ullt a,mod_ullt b){return a.v>b.v;}
friend bol operator<=(mod_ullt a,mod_ullt b){return a.v<=b.v;}
friend bol operator>=(mod_ullt a,mod_ullt b){return a.v>=b.v;}
friend bol operator==(mod_ullt a,mod_ullt b){return a.v==b.v;}
friend bol operator!=(mod_ullt a,mod_ullt b){return a.v!=b.v;}
inline friend mod_ullt operator+(mod_ullt a,mod_ullt b){return a._chg(a.v+b.v);}
inline friend mod_ullt operator-(mod_ullt a,mod_ullt b){return a._chg(a.v+a.chg(p-b.v));}
inline friend mod_ullt operator*(mod_ullt a,mod_ullt b){return a.v*b.v;}
friend mod_ullt operator/(mod_ullt a,mod_ullt b){return b._power(p-2)*a.v;}
friend mod_ullt operator^(mod_ullt a,ullt b){return a._power(b);}
inline mod_ullt operator-(){return _chg(p-v);}
mod_ullt sqrt()
{
if(power(v,(p-1)>>1,p)!=1)return 0;
mod_ullt b=1;do b++;while(b._power((p-1)>>1)==1);
ullt t=p-1,s=0,k=1;while(!(t&1))s++,t>>=1;
mod_ullt x=_power((t+1)>>1),e=_power(t);
while(k<s)
{
if(e._power(1llu<<(s-k-1))!=1)x*=b._power((1llu<<(k-1))*t);
e=_power(p-2)*x*x,k++;
}
return _min(x,-x),x;
}
mod_ullt inv(){return _power(p-2);}
mod_ullt _power(ullt index){mod_ullt ans(1),w(v);while(index){if(index&1)ans*=w;w*=w,index>>=1;}return ans;}
voi read(){v=0;chr c;do c=getchar();while(c>'9'||c<'0');do v=(c-'0'+v*10)%p,c=getchar();while(c>='0'&&c<='9');v%=p;}
voi print()
{
static chr C[20];uint tp=0;
ullt w=v;do C[tp++]=w%10+'0',w/=10;while(w);
while(tp--)putchar(C[tp]);
}
voi println(){print(),putchar('\n');}
mod_ullt operator++(int){mod_ullt ans=*this;return v=chg(v+1),ans;}
public:
inline ullt&operator()(){return v;}
inline mod_ullt&operator+=(mod_ullt b){return*this=_chg(v+b.v);}
inline mod_ullt&operator-=(mod_ullt b){return*this=_chg(v+chg(p-b.v));}
inline mod_ullt&operator*=(mod_ullt b){return*this=v*b.v;}
mod_ullt&operator^=(ullt b){return*this=_power(b);}
mod_ullt&operator/=(mod_ullt b){return*this=b._power(p-2)*v;}
mod_ullt&operator++(){return v=chg(v+1),*this;}
};
}
const ullt Mod=998244353;
typedef ConstMod::mod_ullt<Mod>modint;
typedef std::vector<modint>modvec;
typedef modvec poly;
poly Mul(poly a,poly b)
{
poly ans(a.size()+b.size()-1);
for(uint i=0;i<a.size();i++)for(uint j=0;j<b.size();j++)ans[i+j]+=a[i]*b[j];
return ans;
}
std::vector<uint>Way[1005],RWay[1005];
modint P[3][1005];
modint Inv[3000005];
poly get(uint p,uint f)
{
poly A({0,P[0][p],2*P[1][p],3*P[2][p]});
for(auto s:Way[p])if(s!=f)A=Mul(A,get(s,p));
for(auto s:RWay[p])if(s!=f)
{
poly B=get(s,p);
modint s;
for(auto&v:B)s+=v,v=-v;
B[0]+=s;
A=Mul(A,B);
}
for(uint i=1;i<A.size();i++)A[i]*=Inv[i];
return A;
}
int main()
{
#ifdef MYEE
freopen("QAQ.in","r",stdin);
freopen("QAQ.out","w",stdout);
#endif
Inv[1]=1;for(uint i=2;i<=3000000;i++)Inv[i]=-Inv[Mod%i]*(Mod/i);
uint n;scanf("%u",&n);
modint v;
for(uint i=0;i<n;i++)
P[0][i].read(),P[1][i].read(),P[2][i].read(),v=Inv[(P[0][i]+P[1][i]+P[2][i])()],P[0][i]*=v,P[1][i]*=v,P[2][i]*=v;
for(uint i=1,u,v;i<n;i++)scanf("%u%u",&u,&v),Way[--u].push_back(--v),RWay[v].push_back(u);
poly A=get(0,-1);v=0;
for(uint i=0;i<A.size();i++)v+=A[i];
v.println();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 5
Accepted
time: 91ms
memory: 26208kb
input:
15 537615 525375 879266 999815 627187 383569 750656 124427 861341 544405 209775 52263 697029 306637 542580 790280 87021 601040 894127 170225 886416 638984 591447 777118 164483 157397 335940 437516 568484 864633 760855 106099 908507 158619 105913 535693 60687 856570 178619 440527 919474 388394 492791...
output:
432602958
result:
ok 1 number(s): "432602958"
Test #2:
score: 5
Accepted
time: 78ms
memory: 26428kb
input:
15 800440 684127 181122 115351 869810 527356 574884 33901 497963 918745 844846 673310 555695 775177 508947 420569 628789 828516 47957 761585 577079 620247 552603 501686 110978 50241 941534 301004 832867 87453 780549 151805 290079 480170 267156 678389 526026 842040 712290 542488 760784 75634 215797 8...
output:
561543918
result:
ok 1 number(s): "561543918"
Test #3:
score: 5
Accepted
time: 95ms
memory: 26260kb
input:
15 508072 396849 134954 111049 165872 234704 571453 367377 774557 557624 338462 433791 506099 618139 903497 139381 638125 134361 115544 563280 12695 680331 306691 578616 583944 98313 687 134953 176322 638430 931197 202893 553778 584650 313942 719650 337853 403895 87026 112410 961519 943989 64700 467...
output:
420458731
result:
ok 1 number(s): "420458731"
Test #4:
score: 5
Accepted
time: 85ms
memory: 26488kb
input:
15 676552 125882 520611 9244 110963 50482 482747 101198 550427 921961 546248 958710 653284 656476 870640 995005 911324 465017 114474 341541 52475 492172 12979 887151 321822 727399 792485 253128 7795 617596 236705 684347 743478 275815 693592 372941 326298 176338 474139 876725 616799 538887 835435 788...
output:
767817154
result:
ok 1 number(s): "767817154"
Test #5:
score: 5
Accepted
time: 107ms
memory: 26448kb
input:
196 318318 979071 732191 834476 255393 478338 745819 905706 683633 743759 585426 787752 712543 790957 700984 852752 497151 106339 726547 44400 799000 555784 485531 124665 864563 181229 688654 959110 161456 596401 382249 998274 575471 114440 832750 830864 111277 578568 255069 313410 840826 840495 101...
output:
543350719
result:
ok 1 number(s): "543350719"
Test #6:
score: 5
Accepted
time: 108ms
memory: 26640kb
input:
196 75586 108297 430037 393795 896988 134748 46976 306489 949082 396087 980511 190727 974665 878448 128036 449929 526904 744165 607715 130404 318028 551103 503976 464072 563309 447770 961544 692932 672444 793647 195076 266529 901944 143612 660325 317430 278360 707301 623920 745941 621887 122929 4551...
output:
355663747
result:
ok 1 number(s): "355663747"
Test #7:
score: 5
Accepted
time: 109ms
memory: 26652kb
input:
196 133093 453754 442782 845214 114229 393803 732107 800732 750133 69475 619360 947946 393015 197390 305991 271016 433367 116691 929863 965843 231485 809952 203522 591131 181440 614906 88204 615173 410126 326583 871131 61719 780337 313912 906933 894566 226214 157538 695297 976347 745513 833156 92429...
output:
82980388
result:
ok 1 number(s): "82980388"
Test #8:
score: 5
Accepted
time: 113ms
memory: 26688kb
input:
980 702107 775351 813244 644573 544204 743571 921354 33230 224355 701586 411467 167709 246606 594393 708446 315117 365431 562987 607095 352309 389062 248168 900165 901147 235117 310813 822483 716811 160087 237084 948253 380694 530934 761496 25266 593637 505066 946620 626868 729422 166705 556834 4156...
output:
140401799
result:
ok 1 number(s): "140401799"
Test #9:
score: 5
Accepted
time: 114ms
memory: 26960kb
input:
980 354252 306321 989298 917749 43127 139199 935051 302749 308302 682272 100414 929308 773782 726629 230036 403947 701317 49306 426067 369967 663027 40505 117672 136069 930688 674549 267926 825474 174116 290944 372957 528368 115764 880754 446116 158892 19952 899667 980141 846755 100437 599054 776062...
output:
35624994
result:
ok 1 number(s): "35624994"
Test #10:
score: 5
Accepted
time: 115ms
memory: 26788kb
input:
980 247763 98555 312302 841075 546307 387873 956562 233489 637106 541905 482469 790594 1482 344921 911051 595510 599966 872898 997072 510317 632085 309390 29267 197608 965824 12558 215561 959687 550792 41175 431850 798556 658230 262651 158129 204536 650525 633190 956526 806130 175094 438994 115222 1...
output:
684688579
result:
ok 1 number(s): "684688579"
Test #11:
score: 5
Accepted
time: 104ms
memory: 26856kb
input:
980 682444 908588 42464 396456 70772 436512 779149 460675 638420 761901 420864 106064 886126 785721 162525 437380 341115 191293 670839 515667 296181 333055 964192 762575 956536 173148 821312 960880 851613 982773 932254 534056 409859 493217 449011 999132 448229 228160 459806 605148 508560 399169 7112...
output:
777994448
result:
ok 1 number(s): "777994448"
Test #12:
score: 5
Accepted
time: 97ms
memory: 26416kb
input:
196 823442 204748 87900 857762 809022 604620 241355 405180 92327 791071 194510 805443 92193 202680 505030 135204 501043 288580 62782 928115 627791 797161 518152 833497 533321 735539 779645 281611 357048 718606 568623 180489 441853 656523 556751 250874 261142 798106 174553 871970 107675 369064 677412...
output:
556668257
result:
ok 1 number(s): "556668257"
Test #13:
score: 5
Accepted
time: 91ms
memory: 26444kb
input:
196 612986 938119 652061 926817 557281 176355 673553 979648 177659 860452 707429 250533 657184 926863 931179 173850 724083 893951 517183 892713 153255 504326 938540 304823 141011 215060 249908 896909 793295 302238 815332 406280 240357 467392 851597 797638 643747 525149 777286 821406 904100 3213 5904...
output:
647532378
result:
ok 1 number(s): "647532378"
Test #14:
score: 5
Accepted
time: 95ms
memory: 26416kb
input:
196 695926 112897 107817 11284 92958 912864 927609 313908 521329 437493 139532 323043 715912 146929 496618 195200 519240 330280 2334 984195 36284 50050 900089 712310 116257 930273 560790 646813 633208 458000 807069 329133 570898 914887 858917 663856 827750 786525 977764 349078 742518 635795 672122 4...
output:
16412812
result:
ok 1 number(s): "16412812"
Test #15:
score: 5
Accepted
time: 93ms
memory: 26560kb
input:
980 451307 14540 389421 803774 263141 656195 138160 583300 28807 371124 495661 657258 808815 934640 121704 504946 662687 196695 29903 29370 541823 104152 164387 850602 586476 461313 570762 255471 345794 71763 132385 797101 604804 521807 119374 867945 696501 776034 969744 725309 147158 465405 901066 ...
output:
256917645
result:
ok 1 number(s): "256917645"
Test #16:
score: 5
Accepted
time: 124ms
memory: 26592kb
input:
980 968653 620035 473839 845410 860992 997439 555636 877913 752597 215104 615490 568010 475168 928938 988285 787800 541125 763269 442513 994968 276328 63754 250190 415024 593043 387451 195706 342485 187438 523463 628939 674590 661997 621277 519999 522988 618715 75635 919401 889811 290739 534890 9763...
output:
446042436
result:
ok 1 number(s): "446042436"
Test #17:
score: 5
Accepted
time: 103ms
memory: 26640kb
input:
980 761375 345096 362505 157107 582750 537401 999959 121023 723057 774005 239181 308744 243563 747452 379523 857520 888711 918313 88359 964895 391849 524547 170706 196595 468303 488455 424200 151471 407194 727180 537879 168568 590775 900385 325675 173524 956285 844134 813047 197840 136637 52227 5065...
output:
463488302
result:
ok 1 number(s): "463488302"
Test #18:
score: 5
Accepted
time: 113ms
memory: 26784kb
input:
980 360657 581984 770817 229803 272412 770528 288676 778376 847430 298819 390179 573621 74953 60514 188681 296353 804866 27086 385233 871010 638537 634642 875941 720978 224197 389998 127397 138432 124971 798592 651491 4128 380575 940807 752431 171486 711334 559606 949863 558763 858425 340041 650883 ...
output:
964577860
result:
ok 1 number(s): "964577860"
Test #19:
score: 5
Accepted
time: 100ms
memory: 26500kb
input:
980 495054 79681 193428 630845 962957 551191 879023 983009 962592 28015 759620 364533 956201 42050 196229 27144 596922 890243 396766 886497 40600 450372 221729 831355 111207 376779 667368 474207 932318 888411 731704 945872 486591 443631 576716 968047 994822 455738 951056 475912 483753 710675 358944 ...
output:
775346672
result:
ok 1 number(s): "775346672"
Test #20:
score: 5
Accepted
time: 100ms
memory: 26576kb
input:
980 217886 987275 468613 76186 153289 941627 176949 519092 468976 146733 465921 287029 797492 593929 69809 958372 520568 661150 580270 802433 496378 206349 367208 652335 575377 546364 661201 985062 898845 663399 676648 635231 650674 145260 711417 322462 605386 888366 841555 592862 553598 825975 8798...
output:
426258702
result:
ok 1 number(s): "426258702"
Extra Test:
score: 0
Extra Test Passed