QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#44281#2680. 白兔之舞myee100 ✓560ms36616kbC++1110.6kb2022-08-14 21:05:212022-08-14 21:05:24

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-14 21:05:24]
  • Judged
  • Verdict: 100
  • Time: 560ms
  • Memory: 36616kb
  • [2022-08-14 21:05:21]
  • Submitted

answer

// 10min IP 赋,30min 白兔之舞
#include <algorithm>
#include <math.h>
#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 power(T base,T index,T mod){return((index<=1)?(index?base:1):(power(base*base%mod,index>>1,mod)*power(base,index&1,mod)))%mod;}
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)return y=0,x=1,a;T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}
const dbl Pi=acos(-1);
class cpx
{
    public:
        dbl a,b;
        cpx():a(0),b(0){}
        cpx(dbl a):a(a),b(0){}
        cpx(dbl a,dbl b):a(a),b(b){}
        voi unit(dbl alpha){a=cos(alpha),b=sin(alpha);}
        cpx friend operator+(cpx a,cpx b){return cpx(a.a+b.a,a.b+b.b);}
        cpx friend operator-(cpx a,cpx b){return cpx(a.a-b.a,a.b-b.b);}
        cpx operator-(){return cpx(-a,-b);}
        cpx friend operator*(cpx a,cpx b){return cpx(a.a*b.a-a.b*b.b,a.b*b.a+b.b*a.a);}
        cpx friend operator/(cpx a,ullt v){return cpx(a.a/v,a.b/v);}
        cpx conj(){return cpx(a,-b);}
        cpx mul_i(){return cpx(-b,a);}
        cpx div_i(){return cpx(b,-a);}
    public:
        cpx&operator=(ullt v){return a=v,b=0,*this;}
        cpx&operator+=(cpx v){return*this=*this+v;}
        cpx&operator-=(cpx v){return*this=*this-v;}
        cpx&operator*=(cpx v){return*this=*this*v;}
        cpx&operator/=(ullt v){return a/=v,b/=v,*this;}
        dbl&real(){return a;}
        dbl&imag(){return b;}
};
ullt Mod=998244353;
ullt chg(ullt v){return(v<Mod)?v:v-Mod;}
class poly
{
    private:
        std::vector<ullt>V;
    public:
        class FFT
        {
            private:
                std::vector<uint>V;std::vector<cpx>G;uint len;
            public:
                uint length(){return len;}
                voi bzr(uint length)
                {
                    uint p=0;len=1,V.clear(),G.clear();
                    while(length){p++,len<<=1,length>>=1;}
                    V.resize(len),G.resize(len);
                    for(uint i=0;i<len;++i)V[i]=((i&1)?(V[i>>1]|len)>>1:(V[i>>1]>>1)),G[i].unit(Pi*2/len*i);
                }
                voi fft(std::vector<cpx>&y,bol op)
                {
                    if(y.size()<len)y.resize(len);
                    for(uint i=0;i<len;i++)if(V[i]<i)std::swap(y[i],y[V[i]]);
                    for(uint h=2;h<=len;h<<=1)for(uint j=0;j<len;j+=h)for(uint k=j;k<j+(h>>1);k++){cpx u=y[k],t=G[len/h*(k-j)]*y[k+h/2];y[k]=u+t,y[k+h/2]=u-t;}
                    if(op){uint l=1,r=len-1;while(l<r)std::swap(y[l++],y[r--]);for(uint i=0;i<len;i++)y[i]/=len;}
                }
                voi fft_fft(std::vector<cpx>&a,std::vector<cpx>&b,bol op)
                {
                    if(a.size()<len)a.resize(len);
                    if(b.size()<len)b.resize(len);
                    for(uint i=0;i<len;i++)a[i]+=b[i].mul_i();
                    fft(a,op),b[0]=a[0].conj();for(uint i=1;i<len;i++)b[i]=a[len-i].conj();
                    for(uint i=0;i<len;i++){cpx p=a[i],q=b[i];a[i]=(p+q)/2llu,b[i]=(p-q).div_i()/2llu;}
                }
        };
    public:
        poly(){V.clear();}
        poly(std::vector<ullt>V){for(uint i=0;i<V.size();i++)push(V[i]%Mod);cut_zero();}
        bol empty(){return cut_zero(),!size();}
        voi bzr(){V.clear();}
        voi push(ullt v){V.push_back(v%Mod);}
        voi pop(){V.pop_back();}
        ullt val(uint n){return(n<V.size())?V[n]:0;}
        uint deg(){return V.size()-1;}
        uint size(){return V.size();}
        voi add(uint p,ullt v)
        {
            if(deg()<p)chg_deg(p);
            V[p]=(V[p]+v)%Mod;
        }
        poly friend operator+(poly a,ullt v){a.add(0,v);return a;}
        poly friend operator+(poly a,poly b)
        {
            uint len=std::max(a.size(),b.size());
            a.chg_siz(len),b.chg_siz(len);
            for(uint i=0;i<len;i++)a[i]=chg(a[i]+b[i]);
            a.cut_zero();
            return a;
        }
        poly friend operator-(poly a,poly b)
        {
            uint len=std::max(a.size(),b.size());
            a.chg_siz(len),b.chg_siz(len);
            for(uint i=0;i<len;i++)a[i]=chg(a[i]+Mod-b[i]);
            a.cut_zero();
            return a;
        }
        poly operator-()
        {
            cut_zero();uint len=size();
            poly ans;ans.chg_siz(len);
            for(uint i=0;i<len;i++)ans[i]=chg(Mod-V[i]);
            return ans;
        }
        poly friend operator*(poly a,poly b)
        {
            FFT s;poly p;
            uint n=a.deg(),m=b.deg(),len;
            s.bzr(n+m+1),len=s.length();
            std::vector<cpx>v1(len),v2(len),v3(len),v4(len);
            for(uint i=0;i<len;i++)v3[i]=cpx(a.val(i)&32767),v1[i]=cpx(a.val(i)>>15),v4[i]=cpx(b.val(i)&32767),v2[i]=cpx(b.val(i)>>15);
            s.fft_fft(v1,v2,0),s.fft_fft(v3,v4,0);
            for(uint i=0;i<len;i++)v4[i]=(v3[i]+v1[i].mul_i())*v4[i],v2[i]=(v3[i]+v1[i].mul_i())*v2[i];
            s.fft(v2,1),s.fft(v4,1),p.chg_deg(n+m);for(uint i=0;i<=n+m;i++)p[i]=(((ullt)(v2[i].b+.5)%Mod<<30)+((ullt)(v2[i].a+v4[i].b+.5)%Mod<<15)+(ullt)(v4[i].a+.5))%Mod;
            p.cut_zero();
            return p;
        }
        poly inv(){return inv(size());}
        poly inv(uint prec)
        {
            poly ans,f,tmp,w;
            llt x,y;
            exgcd<llt>(val(0),Mod,x,y);
            ans.push(x%(llt)Mod+(llt)Mod),f.push(val(0));
            for(uint k=1;k<prec;k<<=1)
            {
                for(uint i=k;i<(k<<1);++i)f.push(val(i));
                tmp=f*ans,tmp.chg_siz(k<<1),w.bzr();for(uint i=0;i<k;++i)w.push(tmp[i+k]);
                w*=ans;for(uint i=0;i<k;++i)ans.push(Mod-w[i]);
            }
            return ans;
        }
        poly diff(){uint n=size();poly ans;for(uint i=1;i<n;++i)ans.push(V[i]*i);return ans;}
        poly inte()
        {
            uint n=size();
            poly ans;
            ans.chg_deg(n);
            ullt k=1;llt x,y;
            std::vector<ullt>W;W.push_back(1),W.push_back(1);
            for(uint i=2;i<n;++i)W.push_back(k=(k*i)%Mod);
            exgcd<llt>(k*n%Mod,Mod,x,y);
            k=chg(x%(llt)Mod+(llt)Mod);
            for(uint i=n;i;--i)ans[i]=V[i-1]*k%Mod*W[i-1]%Mod,k=k*i%Mod;
            return ans;
        }
        poly ln(){return(this->diff()*this->inv()).inte().chg_deg_ed(deg());}
        poly exp(){return exp(size());}
        poly exp(uint prec)
        {
            poly m;m.push(1);
            if(empty())return m;
            uint tp=1;
            while(tp<prec)m*=*this-(m.diff()*m.inv(tp<<=1)).inte()+1,m.chg_siz(tp);
            m.chg_siz(prec);
            return m;
        }
        poly reverse(){poly ans;for(uint i=deg();~i;--i)ans.push(V[i]);return ans;}
        poly operator/(poly b)
        {
            cut_zero(),b.cut_zero();uint m=size(),n=b.deg();if(m<=n)return poly();
            poly f=this->reverse()*b.reverse().inv(m-n);f.chg_siz((m>n)?m-n:0);return f.reverse();
        }
        poly operator%(poly b){poly f=*this-*this/b*b;f.cut_zero();return f;}
        voi cut_zero(){while(!V.empty()&&!V.back())V.pop_back();}
        voi chg_siz(const uint siz){while(V.size()<siz)V.push_back(0);while(V.size()>siz)V.pop_back();}
        voi chg_deg(const uint d){chg_siz(d+1);}
        poly chg_deg_ed(const uint d){poly ans=*this;return ans.chg_deg(d),ans;}
    public:
        ullt&operator[](uint num){return V[num];}
        poly&operator=(std::vector<ullt>V){bzr();for(uint i=0;i<V.size();i++)push(V[i]%Mod);cut_zero();return*this;}
        poly&operator=(std::vector<cpx>V){bzr();for(uint i=0;i<V.size();i++)push((llt)(V[i].a+.5)%(llt)Mod+(llt)(Mod));cut_zero();return*this;}
        poly&operator+=(poly b){return*this=*this+b;}
        poly&operator-=(poly b){return*this=*this-b;}
        poly&operator*=(poly b){return*this=*this*b;}
        poly&operator/=(poly b){return*this=*this/b;}
        poly&operator%=(poly b){return*this=*this%b;}
};
const uint Lim=3;
struct Mat
{
    ullt A[Lim][Lim];
    Mat(bol b=false)
    {
        for(uint i=0;i<Lim;i++)
            for(uint j=0;j<Lim;j++)
                A[i][j]=b&&i==j;
    }
    ullt*operator[](uint num){return A[num];}
    friend Mat operator+(Mat a,Mat b)
    {
        for(uint i=0;i<Lim;i++)for(uint j=0;j<Lim;j++)a[i][j]=(a[i][j]+b[i][j])%Mod;
        return a;
    }
    friend Mat operator*(Mat a,ullt v)
    {
        for(uint i=0;i<Lim;i++)for(uint j=0;j<Lim;j++)a[i][j]=a[i][j]*v%Mod;
        return a;
    }
    friend Mat operator*(Mat a,Mat b)
    {
        Mat ans(0);
        for(uint i=0;i<Lim;i++)for(uint j=0;j<Lim;j++)for(uint k=0;k<Lim;k++)ans[i][k]=(ans[i][k]+a[i][j]*b[j][k])%Mod;
        return ans;
    }
};
Mat W(0);
ullt w1[200005],w2[200005],invw1[200005],invw2[200005];
ullt gotg()
{
    ullt Fac[15];uint cnt=0;
    ullt v=Mod-1;
    for(ullt i=2;i*i<=v;i++)
        if(!(v%i))
        {
            Fac[cnt++]=i;
            do v/=i;while(!(v%i));
        }
    if(v>1)Fac[cnt++]=v;
    for(ullt ans=2;;ans++)if(power<ullt>(ans,Mod-1,Mod)==1)
    {
        bol b=true;
        for(uint i=0;b&&i<cnt;i++)if(power<ullt>(ans,(Mod-1)/Fac[i],Mod)==1)b=false;
        if(b)return ans;
    }
    return 0;
}
Mat _power(Mat b,ullt D)
{
    Mat ans(1);
    while(D)
    {
        if(D&1)ans=ans*b;
        b=b*b,D>>=1;
    }
    return ans;
}
poly P,Q;
int main()
{
    uint n,k,l,x,y;
    scanf("%u%u%u%u%u%llu",&n,&k,&l,&x,&y,&Mod),x--,y--;
    ullt w=power<ullt>(gotg(),(Mod-1)/k,Mod);
    ullt invw=power<ullt>(w,Mod-2,Mod);
    ullt invk=power<ullt>(k,Mod-2,Mod);
    w1[0]=w2[0]=invw1[0]=invw2[0]=1;
    for(uint i=1;i<=(k<<1)+5;i++)w1[i]=w1[i-1]*w%Mod,w2[i]=w2[i-1]*w1[i-1]%Mod,invw1[i]=invw1[i-1]*invw%Mod,invw2[i]=invw2[i-1]*invw1[i-1]%Mod;
    for(uint i=0;i<n;i++)for(uint j=0;j<n;j++)scanf("%llu",W[i]+j);
    for(uint i=0;i<k;i++)P.push(_power(W*w1[i]+Mat(1),l)[x][y]*w2[i]);
    for(uint i=0;i<(k<<1);i++)Q.push(invw2[i]);
    Q*=P.reverse();
    for(uint i=0;i<k;i++)printf("%llu\n",Q[i+k-1]*w2[i]%Mod*invk%Mod);
    return 0;
}

/*
Input:
2 2 3 1 1 998244353
2 1
1 0

Output:
16
18
*/
/*
Input:
3 4 100 1 3 998244353
1 1 1
1 1 1
1 1 1

Output:
506551216
528858062
469849094
818871911

*/

詳細信息

Test #1:

score: 10
Accepted
time: 353ms
memory: 35436kb

input:

3 60868 28281 3 2 997261313
541377333 663518765 140473546
710072468 931907445 481102683
305037615 409799686 182541807

output:

0
371201393
126497496
594163146
697376876
913426334
898074565
482372234
553603826
843803081
795054178
946616702
269569577
553650707
14378087
357646765
564252630
697568136
993140951
343394961
414668895
417765343
92116860
146582844
341872589
91292219
712827656
498229323
241600152
737288617
254539718
9...

result:

ok 60868 lines

Test #2:

score: 10
Accepted
time: 340ms
memory: 35620kb

input:

3 60868 87117 3 1 997261313
412700968 717333471 192489438
784392110 821696732 949091933
8361642 752502310 726930970

output:

60292029
640058087
11869095
692950164
540255580
274945329
344271461
515156609
786913720
302417103
43125545
121340671
852329433
394240881
571499679
696088201
191167049
28312047
176057142
187453653
490465175
467256847
482467239
348351209
677628859
813953176
188575598
201611081
640784216
968267076
1413...

result:

ok 60868 lines

Test #3:

score: 10
Accepted
time: 496ms
memory: 36616kb

input:

1 65536 10016911 1 1 997261313
1

output:

95843364
604535263
278366891
990783492
2013628
720647951
9260535
397238127
311690875
773420012
326853860
692389918
315500076
105704504
751724490
885113402
971058219
753283685
830706099
992172799
510959507
779231534
486947229
595061980
133533140
340403360
676742710
506799685
703764431
62824135
798645...

result:

ok 65536 lines

Test #4:

score: 10
Accepted
time: 539ms
memory: 36224kb

input:

1 65536 20544218 1 1 997261313
437647132

output:

644200509
620303851
631204326
481112310
633811411
47942651
870331459
763437565
172267405
581731002
233205140
866042462
774975952
409136314
656136560
476030975
32787014
637953333
511114838
747258841
945232673
153801883
699826168
918103992
547213941
848497521
306040492
225051009
962427223
183330485
51...

result:

ok 65536 lines

Test #5:

score: 10
Accepted
time: 386ms
memory: 34560kb

input:

1 50906 10066288 1 1 776061971
1

output:

587546528
648109148
203519454
618809217
561247059
392172323
324114334
222949490
742797194
547100261
11014982
421541812
582795224
716823937
25648548
214150449
697360571
594557841
651950932
41418218
153610899
204123592
24715666
8410123
759887416
132780989
46436790
632444086
144127670
491389250
5337506...

result:

ok 50906 lines

Test #6:

score: 10
Accepted
time: 395ms
memory: 34760kb

input:

1 50906 14193447 1 1 776061971
7058676

output:

622053597
226388745
107456395
772882966
516527131
362044491
501854798
555831338
617626934
183730318
471355715
54201624
217533864
517954364
272802736
683163272
369123396
272240181
670918454
110963041
632293751
560348804
131349397
328791414
175758401
437413189
5024484
446207973
433731989
733639742
319...

result:

ok 50906 lines

Test #7:

score: 10
Accepted
time: 560ms
memory: 36384kb

input:

2 65536 15489019 1 2 997261313
81819404 229263011
752816130 408725138

output:

948922822
881727936
371493974
295912036
950158243
46531115
439263057
249899778
703170119
106464646
348496160
432112465
428064343
19164663
978200427
773335714
71959766
593295960
82929953
180614969
227338012
401222026
53243774
262385820
745500181
971063406
413682103
441419458
42558924
850605678
568727...

result:

ok 65536 lines

Test #8:

score: 10
Accepted
time: 496ms
memory: 36360kb

input:

2 65536 69511249 1 1 997261313
500289590 382459525
578601485 187892897

output:

701570973
716226039
234558373
409288946
685028963
515183831
272484358
358892317
462512496
531428570
135278492
429845293
258070966
537880616
227630813
850882358
831992488
388830173
716273894
788299005
432448404
551570192
541908616
420756187
464408237
499641174
935462688
689939480
793103718
384814016
...

result:

ok 65536 lines

Test #9:

score: 10
Accepted
time: 426ms
memory: 35036kb

input:

3 50906 57946722 1 1 776061971
647247752 742197886 79186200
237641887 308607445 80891991
134069917 377341939 143644495

output:

391258133
308185474
168324843
637959251
13075041
222908554
120394561
337546139
312429906
321748004
554021806
667266193
526683824
267035369
686212061
164671063
276963438
625212216
592259777
521994264
739689256
597120742
20522119
267718539
23185084
116169623
360516396
96978312
693315693
674591278
5053...

result:

ok 50906 lines

Test #10:

score: 10
Accepted
time: 425ms
memory: 34796kb

input:

3 50906 93980303 1 2 776061971
505745611 708180844 233942141
7793688 560919932 211232826
486943270 62469440 149793907

output:

229837759
359420333
76590438
374230202
748301690
445720367
122793822
100194533
756172749
331945823
141777464
243199309
246386756
644556570
250294271
101508810
720333206
46422072
153889553
494223906
772263462
469768946
259885781
298581507
401062551
229166351
514521886
398898312
720667125
765488168
29...

result:

ok 50906 lines