[HNOI2019]白兔之舞
2024-10-08 02:54:09
多合一无聊题
mod k=t，并且k是p-1的约数
单位根反演石锤了。
所以直接设f[i]表示走i步的方案数，
然后C(L,i)分配位置，再A^i进行矩乘得到f[i]
变成生成函数F(x)=∑f[i]=(A*x+I)^L
求指数mod k=t的系数的和
偏移之后，进行单位根反演
对于t都要求？
NTT
然后WA了
因为要任意模数NTT，。。。。
然后套用全家桶有了9K的代码：
#include<bits/stdc++.h>
#define reg register int
#define il inline
#define fi first
#define se second
#define mk(a,b) make_pair(a,b)
#define numb (ch^'0')
using namespace std;
typedef long long ll;
template<class T>il void rd(T &x){
char ch;x=;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*+numb);
(fl==true)&&(x=-x);
}
template<class T>il void output(T x){if(x/)output(x/);putchar(x%+'');}
template<class T>il void ot(T x){if(x<) putchar('-'),x=-x;output(x);putchar(' ');}
template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}
//--------------------------------------------------------------------------------------------------------------------//
namespace Miracle{
const int N=*;
int mod,w;
int X,L,Y,K,G,GI;
const double Pi=acos(-);
il int qm(int x,ll y){int ret=;while(y){if(y&) ret=(ll)ret*x%mod;x=(ll)x*x%mod;y>>=;}return ret;}
il int ad(int x,int y){return x+y>=mod?x+y-mod:x+y;}
il int sub(int x,int y){return ad(x,mod-y);}
il int mul(int x,int y){return (ll)x*y%mod;}
struct tr{
int a[][];
tr(){memset(a,,sizeof a);}
void init(){
a[][]=a[][]=a[][]=;
}
tr friend operator *(const tr &a,const tr &b){
tr c;
for(reg i=;i<;++i){
for(reg k=;k<;++k){
for(reg j=;j<;++j){
c.a[i][j]=ad(c.a[i][j],mul(a.a[i][k],b.a[k][j]));
}
}
}return c;
}
tr friend operator +(const tr &a,const tr &b){
tr c;
for(reg i=;i<;++i){
for(reg j=;j<;++j){
c.a[i][j]=ad(a.a[i][j],b.a[i][j]);
}
}
return c;
}
tr friend operator -(const tr &a,const tr &b){
tr c;
for(reg i=;i<;++i){
for(reg j=;j<;++j){
c.a[i][j]=ad(a.a[i][j],mod-b.a[i][j]);
}
}
return c;
}
tr friend operator *(const tr &a,const int &v){
tr c;
for(reg i=;i<;++i){
for(reg j=;j<;++j){
c.a[i][j]=mul(a.a[i][j],v);
}
}
return c;
}
void out(){
for(reg i=;i<;++i){
for(reg j=;j<;++j){
cout<<a[i][j]<<" ";
}cout<<endl;
}
}
}S,A,I,B,c[N],ans[N];
tr qm(tr x,int y){
tr ret;ret.init();
while(y){
if(y&) ret=ret*x;
x=x*x;
y>>=;
}
return ret;
} namespace Polynomial{
struct Poly{
vector<int>f;
Poly(){f.clear();}
il int &operator[](const int &x){return f[x];}
il const int &operator[](const int &x) const {return f[x];}
il void resize(const int &n){f.resize(n);}
il int size() const {return f.size();}
il void cpy(Poly &b){f.resize(b.size());for(reg i=;i<(int)f.size();++i)f[i]=b[i];}
il void rev(){reverse(f.begin(),f.end());}
il void clear(){f.clear();}
il void read(const int &n){f.resize(n);for(reg i=;i<n;++i)rd(f[i]);}
il void out() const {for(reg i=;i<(int)f.size();++i)ot(f[i]);putchar('\n');}
}R;
il int init(const int &n){int m;for(m=;m<n;m<<=);return m;}
template<class T>il void rev(T &f){
int lp=f.size();
if(R.size()!=f.size()) {
R.resize(f.size());
for(reg i=;i<lp;++i){
R[i]=(R[i>>]>>)|((i&)?lp>>:);
}
}
for(reg i=;i<lp;++i){
if(i<R[i]) swap(f[i],f[R[i]]);
}
}
}
using namespace Polynomial;
//--------------------------------------------------------------------------------------------------------------------//
il void operator +=(Poly &f,const Poly &g){for(reg i=;i<f.size();++i) f[i]=ad(f[i],g[i]);}
il void operator +=(Poly &f,const int &c){f[]=ad(f[],c);}
il Poly operator +(Poly f,const Poly &g){for(reg i=;i<f.size();++i) f[i]=ad(f[i],g[i]);return f;}
il Poly operator +(Poly f,const int &c){f[]=ad(f[],c);return f;}
il void operator -=(Poly &f,const Poly &g){for(reg i=;i<f.size();++i) f[i]=sub(f[i],g[i]);}
il void operator -=(Poly &f,const int &c){f[]=sub(f[],c);}
il Poly operator -(Poly f,const Poly &g){for(reg i=;i<f.size();++i) f[i]=sub(f[i],g[i]);return f;}
il Poly operator -(Poly f,const int &c){f[]=sub(f[],c);return f;}
il Poly operator -(Poly f){for(reg i=;i<f.size();++i) f[i]=mod-f[i];return f;}
//--------------------------------------------------------------------------------------------------------------------//
namespace FastFourierTransform{
struct cplx{
double x,y;
cplx(){x=0.0;y=0.0;}
cplx(double xx,double yy){x=xx;y=yy;}
cplx friend operator !(cplx a){return cplx(a.x,-a.y);}
cplx friend operator +(cplx a,cplx b){return cplx(a.x+b.x,a.y+b.y);}
cplx friend operator -(cplx a,cplx b){return cplx(a.x-b.x,a.y-b.y);}
cplx friend operator *(cplx a,cplx b){return cplx(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
};
struct Cps{
vector<cplx>f;
Cps(){f.clear();}
il cplx &operator[](const int &x){return f[x];}
il const cplx &operator[](const int &x) const {return f[x];}
il void resize(const int &n){f.resize(n);}
il int size() const {return f.size();}
il void cpy(Cps &b){f.resize(b.size());for(reg i=;i<(int)f.size();++i)f[i]=b[i];}
il void rev(){reverse(f.begin(),f.end());}
il void clear(){f.clear();}
il void out(){
for(reg i=;i<(int)f.size();++i){
cout<<"("<<f[i].x<<","<<f[i].y<<") ";
}cout<<endl;
}
}W;
il void FFT(Cps &f,int c){
int n=f.size();rev(f);
for(reg p=;p<=n;p<<=){
int len=p/;
for(reg l=;l<n;l+=p){
for(reg k=l;k<l+len;++k){
cplx tmp=f[k+len]*(c>?W[n/p*(k-l)]:!W[n/p*(k-l)]);
f[k+len]=f[k]-tmp;
f[k]=f[k]+tmp;
}
}
}
if(c==-){
for(reg i=;i<n;++i){
f[i].x/=n;f[i].y/=n;
}
}
}
il void prework(int n){
if(W.size()!=n){
W.resize(n);
for(reg i=;i<n;++i){
W[i]=cplx(cos(*Pi/n*i),sin(*Pi/n*i));
}
}
}
il Poly MTT(const Poly &F,const Poly &G,const int &P){
int n=F.size(),m=G.size();
Cps a,b,c,d;
int len=init(n+m-);
a.resize(len);b.resize(len);
c.resize(len);d.resize(len);
for(reg i=;i<n;++i){
a[i].x=F[i]>>;a[i].y=F[i]&;
}
for(reg i=;i<m;++i){
b[i].x=G[i]>>;b[i].y=G[i]&;
}
prework(len);
FFT(a,);FFT(b,);
cplx ka,kb,ba,bb;
cplx aaa=cplx(0.5,),bbb=cplx(,-0.5),o=cplx(,);
for(reg i=;i<len;++i){
int j=(len-i)%len;
ka=(a[i]+!a[j])*aaa;ba=(a[i]-!a[j])*bbb;
kb=(b[i]+!b[j])*aaa;bb=(b[i]-!b[j])*bbb;
c[i]=ka*kb+ba*kb*o;
d[i]=bb*ka+bb*ba*o;
}
FFT(c,-);FFT(d,-);
Poly ret;
ret.resize(n+m-);
for(reg i=;i<n+m-;++i){
ll A=(ll)(c[i].x+0.5)%P,B=(ll)(c[i].y+0.5)%P;
ll C=(ll)(d[i].x+0.5)%P,D=(ll)(d[i].y+0.5)%P;
ret[i]=((((A<<)%P)+((B+C)<<)%P)%P+D)%P;
}
return ret;
}
il void operator *=(Poly &f,Poly g){
f=MTT(f,g,mod);
}
il void operator *=(Poly &f,const int &c){for(reg i=;i<f.size();++i) f[i]=mul(f[i],c);}
il Poly operator *(Poly f,const Poly &g){f*=g;return f;}
il Poly operator *(Poly f,const int &c){for(reg i=;i<f.size();++i) f[i]=mul(f[i],c);return f;}
il Poly Inv(const Poly &f,int n){
if(n==){
Poly g;g.resize();g[]=qm(f[],mod-);return g;
}
Poly h=Inv(f,(n+)>>);
Poly tmp=h,t;
t.resize(n);
for(reg i=;i<n;++i) t[i]=f[i];
tmp=tmp*tmp*t;
h.resize(tmp.size());
Poly g=h*-tmp;
g.resize(n);
return g;
}
}
using namespace FastFourierTransform;
int pri[N],cnt;
void fin(){
int lp=mod-;
for(reg i=;(ll)i*i<=lp;++i){
if(lp%i==){
++cnt;
pri[cnt]=i;
while(lp%i==) lp/=i;
}
}
if(lp) pri[++cnt]=lp;
// cout<<" cnt "<<cnt<<endl;
// prt(pri,1,cnt);
G=;
lp=mod-;
for(;;++G){
bool fl=true;
for(reg j=;j<=cnt;++j){
if(qm(G,lp/pri[j])==) fl=false;
}
if(fl) break;
}
}
int main(){
int n;
rd(n);rd(K);rd(L);rd(X);rd(Y);rd(mod);
--X;--Y;
fin();
GI=qm(G,mod-);
// cout<<" GG "<<G<<" GI "<<GI<<endl;
for(reg i=;i<n;++i){
for(reg j=;j<n;++j){
rd(A.a[i][j]);
}
}
I.init();
S.a[][X]=;
int now=;
w=qm(G,(mod-)/K);
int T=qm(w,mod-);
for(reg i=;i<K;++i){
c[i]=qm((A*now)+I,L)*qm(w,(ll)i*(i-)/);
now=mul(now,w);
// cout<<" i "<<i<<endl;
// c[i].out();
// cout<<endl;
} Poly g;
g.resize(*K-);
for(reg i=;i<*K-;++i){
g[i]=qm(T,(ll)i*(i-)/);
}
g.rev();
Poly f;
f.resize(*K-); for(reg i=;i<;++i){
int j=Y;
f.clear();
f.resize(*K-);
for(reg k=;k<K;++k){
f[k]=c[k].a[i][j];
}
// f.out();
// g.out();
// cout<<endl;
f*=g;
// cout<<" ff "<<endl;
// f.out();
// cout<<" edn "<<endl;
for(reg k=;k<f.size();++k){
ans[k].a[i][j]=f[k];
}
// for(reg k=0;k<K;++k){
// // cout<<" ans[k] "<<k<<endl;
// // ans[k].out();
// }
}
for(reg t=;t<K;++t){
tr now=ans[*K--t];
// cout<<" tt "<<t<<endl;now.out();
now=now*qm(w,(ll)t*(t-)/)*qm(K,mod-);
tr out=S*now;
// ot(out.a[0][Y]);
printf("%d\n",out.a[][Y]);
}
return ;
} }
signed main(){
Miracle::main();
return ;
} /*
Author: *Miracle*
Date: 2019/4/8 18:57:00
*/
最新文章
- C语言的一些小知识
- cookie的详细解释
- Vrrp协议
- String与StringBuffer对象问题
- 多次绑定click及ajax提交常用方法
- jQuery EasyUI API - Grid - DataGrid [原创汉化官方API]
- BZOJ 1009 ：[HNOI2008]GT考试（KPM算法+dp+矩阵快速幂）
- echarts 点击方法总结，点任意一点获取点击数据，在多图联动中用生成标线举例
- Android的AdapterView及其子类简介-android学习之旅（二十三）
- RabbitMQ消息队列（五）：Routing 消息路由
- jmeter添加断言
- Js中的闭包原理
- 5; XHTML图像
- 2017-2018-2 20165325 实验四《Android程序设计》实验报告
- 机器学习课程-第8周-降维(Dimensionality Reduction)—主成分分析(PCA)
- 如何将SqlServer中表结构以及表数据全部导出
- 旧的flex
- Intersection（Check）
- Teamviewer 手机端怎么拖动窗口，选中文字
- bing词典