QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#44281 | #2680. 白兔之舞 | myee | 100 ✓ | 560ms | 36616kb | C++11 | 10.6kb | 2022-08-14 21:05:21 | 2022-08-14 21:05:24 |
Judging History
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