QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#448926#7775. 【模板】矩阵快速幂Dark_night25 2897ms5212kbC++144.8kb2024-06-20 12:30:172024-06-20 12:30:17

Judging History

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

  • [2024-06-20 12:30:17]
  • 评测
  • 测评结果:25
  • 用时:2897ms
  • 内存:5212kb
  • [2024-06-20 12:30:17]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const ll mod=1e18;
const ll base[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000};
const ll mmd=998244353;

struct Node
{
    ll a[5];

    inline void clear(int op)
    {
        a[0]=a[1]=a[2]=a[3]=a[4]=0;
        if(op)
            a[4]=mod/10;
    }

    inline void print()
    {
        ll rr=0,pk=1;

        for(int i=0;i<5;i++)
        {
            rr=(rr+a[i]%mmd*pk)%mmd;
            pk=mod%mmd*pk%mmd;
        }

        cout<<rr<<' ';
    }
};

Node mx,K,bk[305][305],sum[305][305],res[305],tmp;
__int128 ek=1,qwq[5];
ll ed[305];
int __,_;
int n,m;
char s[75];

inline Node comb(const Node &x,const Node &y)
{
    for(int i=0;i<5;i++)
        tmp.a[i]=x.a[i]+y.a[i];

    for(int i=0;i<4;i++)
    {
        if(tmp.a[i]>=mod)
            tmp.a[i+1]++,tmp.a[i]-=mod;
    }

    return tmp;
}

inline void update(Node &x,const Node &y)
{
    for(int i=4;i;i--)
    {
        if(x.a[i]!=y.a[i])
        {
            if(y.a[i]<x.a[i])
                x=y;
            return;
        }
    }

    if(y.a[0]<x.a[0])
        x=y;
}

inline bool check(const Node &x,ll y){return x.a[1]||x.a[2]||x.a[3]||x.a[4]||x.a[0]>=y;}

inline Node query(int l,int r)
{
    if(l>r)
        swap(l,r);

    tmp.clear(0);

    for(int i=l+1;i<=r;i++)
    {
        tmp.a[0]+=ed[i];
        if(tmp.a[0]>=mod)
            tmp.a[1]++,tmp.a[0]-=mod;
    }

    return tmp;
}

inline Node qmin(const Node &x,ll y)
{
    tmp=x;
    tmp.a[0]-=y;
    for(int i=0;i<4;i++)
    {
        if(tmp.a[i]<0)
        {
            tmp.a[i+1]--;
            tmp.a[i]+=mod;
        }
    }

    return tmp;
}

inline Node tmk(const Node &x,ll y)
{
    for(int i=0;i<5;i++)
        qwq[i]=ek*x.a[i]*y;

    for(int i=0;i<4;i++)
    {
        qwq[i+1]+=qwq[i]/mod;
        tmp.a[i]=qwq[i]%mod;
    }
    tmp.a[4]=qwq[4];

    return tmp;
}

inline void sol()
{
    cin>>n>>m>>(s+1);
    int len=strlen(s+1);

    for(int i=0;i<5;i++)
    {
        int p=0;
        ll tp=0;
        while(p<18&&len)
        {
            tp+=(s[len]-'0')*base[p];
            p++,len--;
        }
        K.a[i]=tp;
    }

    if(__==2)
    {
        while(m--)
        {
            int u,v;
            ll w;
            cin>>u>>v>>w;
            if(u<v)
                ed[v]=w;
        }

        for(int i=1;i<=n;i++)
        {
            if((i&1)==(K.a[0]&1))
            {
                cout<<-1<<' ';
                continue;
            }

            res[0].clear(1);

            for(int j=2;j<=n;j++)
            {
                if(check(K,j-1+abs(i-j)))
                    update(res[0],comb(tmk(qmin(K,j-1+abs(i-j)),ed[j]),comb(query(1,j),query(i,j))));
            }

            if(res[0].a[4]>=mod/10)
                cout<<"-1 ";
            else
                res[0].print();
        }

        cout<<'\n';

        return;
    }

    for(int i=1;i<=n;i++)
    {
        res[i].clear(1);
        for(int j=1;j<=n;j++)
            bk[i][j].clear(1);
    }
    res[1].clear(0);

    while(m--)
    {
        int u,v;
        ll w;
        cin>>u>>v>>w;

        if(check(bk[u][v],w))
        {
            bk[u][v].clear(0);
            bk[u][v].a[0]=w;
            if(bk[u][v].a[0]>=mod)
                bk[u][v].a[1]++,bk[u][v].a[0]-=mod;
        }
    }

    while(check(K,1))
    {
        if(K.a[0]&1)
        {
            for(int i=1;i<=n;i++)
            {
                sum[0][i].clear(1);
                for(int j=1;j<=n;j++)
                    update(sum[0][i],comb(res[j],bk[j][i]));
            }

            for(int i=1;i<=n;i++)
                res[i]=sum[0][i];
        }

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                sum[i][j].clear(1);
                for(int k=1;k<=n;k++)
                    update(sum[i][j],comb(bk[i][k],bk[k][j]));
            }
        }

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
                bk[i][j]=sum[i][j];
        }

        for(int i=4;i;i--)
        {
            if(K.a[i]&1)
                K.a[i-1]+=mod;
            K.a[i]>>=1;
        }
        K.a[0]>>=1;
    }

    for(int i=1;i<=n;i++)
    {
        if(res[i].a[4]>=mod/10)
            cout<<"-1 ";
        else
            res[i].print();
    }

    cout<<'\n';
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    mx.clear(1);

    cin>>__>>_;
    while(_--)
        sol();

    return 0;
}

詳細信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 595ms
memory: 5128kb

input:

1
1
100 101 899539897889989959
74 35 910832669819965536
35 85 910832669819965536
85 88 910832669819965536
88 30 910832669819965536
30 58 910832669819965536
58 60 910832669819965536
60 34 910832669819965536
34 8 910832669819965536
8 67 910832669819965536
67 89 910832669819965536
89 32 910832669819965...

output:

395495792 395495781 395495783 395495839 395495793 395495789 395495754 395495832 395495845 395495755 395495823 395495773 395495753 395495800 395495782 395495763 395495847 395495761 395495794 395495791 395495786 395495821 395495798 395495765 395495772 395495770 395495757 395495819 395495843 395495828 ...

result:

ok 100 numbers

Test #2:

score: 10
Accepted
time: 747ms
memory: 5132kb

input:

1
1
100 200 998858598565699977
89 61 596014036562538539
89 84 921297646113897322
61 84 946923234442637386
61 35 641628261157284465
84 35 979893473772327497
84 78 700172488379560611
35 78 963617193748189613
35 54 951598888254521423
78 54 680825215292116806
78 21 737055858973038555
54 21 7491794406112...

output:

590375247 265938345 203065828 597548045 369717762 226160283 377877020 360218254 956162456 408060901 387231165 759578975 67601808 790211315 608425007 343195480 177353482 436533546 717630459 417099733 542227025 861764246 913806375 587268602 989846681 435016550 66609901 817090566 256847656 844441854 94...

result:

ok 100 numbers

Test #3:

score: 10
Accepted
time: 676ms
memory: 5164kb

input:

1
1
100 181 348568663892999968
25 19 990622898175774733
19 94 871060999389241529
94 24 969317630558501400
24 43 908457844888427461
43 52 816088481082287266
52 62 978618931332609685
62 99 761714433396732044
99 85 741344935503895668
85 64 964684335126604843
64 69 988098065125373655
69 31 7506975506815...

output:

916998469 916998469 916998469 76035207 62461893 916998469 389136594 916998469 916998469 173423529 164423356 822964468 626456020 916998469 744111524 916998469 398953850 916998469 342238577 916998469 255074799 784015663 916998469 740933556 587088671 811719512 916998469 916998469 916998469 916998469 14...

result:

ok 100 numbers

Test #4:

score: 10
Accepted
time: 668ms
memory: 5212kb

input:

1
1
100 189 295064635124730243
18 50 754672892083203214
50 88 962632394366987404
88 15 906700334097319336
15 26 967741400981618572
26 91 996214498763867892
91 35 882157548994344280
35 68 983621159612138407
68 51 563935036482744182
51 75 991205513962219551
75 72 974025375183814852
72 11 7979447663592...

output:

663199381 739882534 663199381 28600701 663199381 944601671 836329160 894091561 629507606 663199381 246830507 663199381 491987421 663199381 802123884 663199381 663199381 663199381 414785533 989396289 663199381 663199381 663199381 663199381 663199381 663199381 663199381 663199381 663199381 663199381 4...

result:

ok 100 numbers

Test #5:

score: 10
Accepted
time: 373ms
memory: 4016kb

input:

1
254
40 74 997173688939799978
38 6 890721839505665075
6 10 992308491267087930
10 29 960202932780090595
29 20 952827125924298715
20 34 868314670055961466
34 31 756448635709788087
31 14 857625921909632516
14 18 917667459973696862
18 21 985939328882662624
21 1 734882468602343649
1 11 66102593854575036...

output:

177014577 177014577 177014577 885341552 472856470 177014577 363547548 177014577 499847464 653076748 177014577 177014577 177014577 177014577 487939796 177014577 213466543 586729345 244952763 177014577 177014577 177014577 177014577 890105934 177014577 177014577 890105934 177014577 177014577 798890006 ...

result:

ok 3575 numbers

Test #6:

score: 10
Accepted
time: 378ms
memory: 3904kb

input:

1
356
32 47 967844399484634837
4 30 776954643355911997
30 20 811634053140142741
20 22 747630229183579429
22 2 806282875388761050
2 26 719793351534499411
26 17 797537828929335673
17 24 890423236992687627
24 21 970792227007588899
21 8 850078803097295262
8 15 958474507028658347
15 1 972636122087215360
...

output:

890097469 525779071 636798453 776362497 776362497 687961593 158033324 776362497 345910504 380622623 239804834 440670451 137231885 985041116 222869127 137231885 705696901 637534644 347889826 696528073 291555427 146553026 776362497 624486185 137231885 642408114 520519927 137231885 438373632 263924254 ...

result:

ok 4784 numbers

Subtask #2:

score: 15
Accepted

Test #7:

score: 15
Accepted
time: 11ms
memory: 3624kb

input:

2
1
300 598 8179377797889487867988994778539839593376697796496698959964978969
1 2 977880533270721156
2 1 977880533270721156
2 3 977880533270721156
3 2 977880533270721156
3 4 977880533270721156
4 3 977880533270721156
4 5 977880533270721156
5 4 977880533270721156
5 6 977880533270721156
6 5 977880533270...

output:

-1 313446627 -1 313436465 -1 313426303 -1 313416141 -1 313405979 -1 313395817 -1 313385655 -1 313375493 -1 313365331 -1 313355169 -1 313345007 -1 313334845 -1 313324683 -1 313314521 -1 313304359 -1 313294197 -1 313284035 -1 313273873 -1 313263711 -1 313253549 -1 313243387 -1 313233225 -1 313223063 -...

result:

ok 300 numbers

Test #8:

score: 15
Accepted
time: 13ms
memory: 3544kb

input:

2
1
300 598 9284745978997975899894787995823975998931999649789777849997467689
1 2 946893593823801228
2 1 946893593823801228
2 3 761384824565158999
3 2 761384824565158999
3 4 642721010434291429
4 3 642721010434291429
4 5 936762490761905983
5 4 936762490761905983
5 6 785485094128355256
6 5 785485094128...

output:

-1 613575042 -1 416269325 -1 387291578 -1 980556870 -1 491367967 -1 221793101 -1 191668085 -1 356035653 -1 428450970 -1 964149805 -1 511723806 -1 423081033 -1 947783979 -1 325795034 -1 115778037 -1 86469999 -1 111666379 -1 386592847 -1 223100328 -1 381885001 -1 23001328 -1 84087613 -1 517941041 -1 9...

result:

ok 300 numbers

Test #9:

score: 15
Accepted
time: 10ms
memory: 3620kb

input:

2
1
300 598 7877597936928589688789427798322599997378688496694695996269389696
1 2 866412995946330002
2 1 866412995946330002
2 3 866412995946330002
3 2 866412995946330002
3 4 866412995946330002
4 3 866412995946330002
4 5 866412995946330002
5 4 866412995946330002
5 6 866412995946330002
6 5 866412995946...

output:

708443714 -1 708438498 -1 708433282 -1 708428066 -1 708422850 -1 708417634 -1 708412418 -1 708407202 -1 708401986 -1 708396770 -1 708391554 -1 708386338 -1 708381122 -1 708375906 -1 708370690 -1 708365474 -1 708360258 -1 708355042 -1 708349826 -1 708344610 -1 708339394 -1 708334178 -1 708328962 -1 7...

result:

ok 300 numbers

Test #10:

score: 15
Accepted
time: 11ms
memory: 3544kb

input:

2
1
300 598 74686617152792803
1 2 920869599353968456
2 1 920869599353968456
2 3 920869599353968456
3 2 920869599353968456
3 4 920869599353968456
4 3 920869599353968456
4 5 920869599353968456
5 4 920869599353968456
5 6 920869599353968456
6 5 920869599353968456
6 7 920869599353968456
7 6 9208695993539...

output:

-1 537762223 -1 537752459 -1 537742695 -1 537732931 -1 537723167 -1 537713403 -1 537703639 -1 537693875 -1 537684111 -1 537674347 -1 537664583 -1 537654819 -1 537645055 -1 537635291 -1 537625527 -1 537615763 -1 537605999 -1 537596235 -1 537586471 -1 537576707 -1 537566943 -1 537557179 -1 537547415 -...

result:

ok 300 numbers

Test #11:

score: 15
Accepted
time: 20ms
memory: 3628kb

input:

2
40
120 238 7647979978895986883485788838258737687493899697379499657768989994
1 2 940784508355800649
2 1 940784508355800649
2 3 940784508355800649
3 2 940784508355800649
3 4 940784508355800649
4 3 940784508355800649
4 5 940784508355800649
5 4 940784508355800649
5 6 940784508355800649
6 5 94078450835...

output:

383704267 -1 383701847 -1 383699427 -1 383697007 -1 383694587 -1 383692167 -1 383689747 -1 383687327 -1 383684907 -1 383682487 -1 383680067 -1 383677647 -1 383675227 -1 383672807 -1 383670387 -1 383667967 -1 383665547 -1 383663127 -1 383660707 -1 383658287 -1 383655867 -1 383653447 -1 383651027 -1 3...

result:

ok 3146 numbers

Test #12:

score: 15
Accepted
time: 88ms
memory: 3560kb

input:

2
5697
96 190 8939398847797777979859997957885578698889795859699765658877967896
1 2 940438543633266209
2 1 940438543633266209
2 3 940438543633266209
3 2 940438543633266209
3 4 940438543633266209
4 3 940438543633266209
4 5 940438543633266209
5 4 940438543633266209
5 6 940438543633266209
6 5 9404385436...

output:

57861585 -1 57859879 -1 57858173 -1 57856467 -1 57854761 -1 57853055 -1 57851349 -1 57849643 -1 57847937 -1 57846231 -1 57844525 -1 57842819 -1 57841113 -1 57839407 -1 57837701 -1 57835995 -1 57834289 -1 57832583 -1 57830877 -1 57829171 -1 57827465 -1 57825759 -1 57824053 -1 57822347 -1 57820641 -1 ...

result:

ok 77560 numbers

Subtask #3:

score: 0
Time Limit Exceeded

Dependency #2:

100%
Accepted

Test #13:

score: 0
Time Limit Exceeded

input:

3
1
300 600 9479768887366979469968967538414386738799799469768954967897479478
235 118 610005418879451235
118 235 610005418879451235
229 118 610005418879451235
118 229 610005418879451235
36 235 610005418879451235
235 36 610005418879451235
265 229 610005418879451235
229 265 610005418879451235
24 36 610...

output:


result:


Subtask #4:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Test #19:

score: 15
Accepted
time: 2897ms
memory: 5200kb

input:

4
1
100 101 6888995999928874698772868926699656683388498575797893294688976887
25 90 495511874996847106
90 84 495511874996847106
84 82 495511874996847106
82 40 495511874996847106
40 97 495511874996847106
97 5 495511874996847106
5 24 495511874996847106
24 16 495511874996847106
16 19 495511874996847106
...

output:

662900138 662900131 662900188 662900147 662900176 662900221 662900152 662900202 662900130 662900140 662900169 662900199 662900128 662900145 662900192 662900178 662900163 662900150 662900179 662900151 662900139 662900180 662900216 662900177 662900170 662900205 662900210 662900183 662900184 662900125 ...

result:

ok 100 numbers

Test #20:

score: 0
Time Limit Exceeded

input:

4
1
100 200 7298898492397999688666927949888498969897838287679988999656889979
1 68 716477084362826727
1 70 849254955511480878
68 70 965501875328180109
68 27 922798232695217800
70 27 973650788054328171
70 69 992887836560799260
27 69 912347321604310534
27 41 707737334645887057
69 41 939222694708421463
...

output:

59219241 402083566 593666306 414807498 258758770 177911843 190858821 427609509 714942754 794670437 266523695 250908431 280340515 973300594 490891479 435411914 570632298 806776572 581872834 661756417 571008187 273666813 634277068 321782154 962526931 884883598 912195600 389101189 783089343 302322065 7...

result:


Subtask #5:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Test #25:

score: 0
Time Limit Exceeded

input:

5
1
300 301 969767789936486493
164 284 964646444984408140
284 241 964646444984408140
241 281 964646444984408140
281 138 964646444984408140
138 242 964646444984408140
242 112 964646444984408140
112 217 964646444984408140
217 170 964646444984408140
170 31 964646444984408140
31 300 964646444984408140
3...

output:


result:


Subtask #6:

score: 0
Skipped

Dependency #3:

0%