QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#108890#4476. 氪金手游myee100 ✓124ms26960kbC++115.2kb2023-05-26 21:10:382023-05-26 21:10:40

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-26 21:10:40]
  • 评测
  • 测评结果:100
  • 用时:124ms
  • 内存:26960kb
  • [2023-05-26 21:10:38]
  • 提交

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;
}

详细

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