AC日记——[SDOI2009]HH去散步 洛谷 P2151

[SDOI2009]HH去散步

思路;

  矩阵快速幂递推(类似弗洛伊德);

  给大佬跪烂~~

代码:

#include <bits/stdc++.h>
using namespace std;
#define mod 45989
struct MatrixType {
int n,m,ai[][];
MatrixType(int n_,int m_)
{
n=n_,m=m_;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)ai[i][j]=;
}
}
MatrixType operator*(const MatrixType pos)const
{
MatrixType res(n,pos.m);
for(int i=;i<=res.n;i++)
for(int j=;j<=res.m;j++)
for(int v=;v<=m;v++)
res.ai[i][j]=(res.ai[i][j]+ai[i][v]*pos.ai[v][j])%mod;
return res;
}
};
int n,m,t,a,b,cnt=-,E[],V[],head[];
bool ma[][];
inline void in(int &now)
{
char Cget=getchar();now=;
while(Cget>''||Cget<'')Cget=getchar();
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
}
MatrixType poww(MatrixType x,MatrixType y,int e)
{
while(e)
{
if(e&) x=x*y;
y=y*y,e>>=;
}
return x;
}
int main()
{
memset(head,-,sizeof(head));
in(n),in(m),in(t),in(a),in(b);
int u,v;
for(int i=;i<=m;i++)
{
in(u),in(v);
E[++cnt]=head[u],V[cnt]=v,head[u]=cnt;
E[++cnt]=head[v],V[cnt]=u,head[v]=cnt;
}
MatrixType bi(cnt,cnt);
for(int i=;i<=cnt;i++)
{
for(int v=head[V[i]];v!=-;v=E[v])
{
if(v!=(i^)) bi.ai[i][v]++;
}
}
MatrixType ai(,cnt);
for(int i=head[a];i!=-;i=E[i]) ai.ai[][i]++;
MatrixType ans=poww(ai,bi,t-);
int ans_=;
for(int i=;i<=ans.m;i++) if(V[i]==b)ans_=(ans_+ans.ai[][i])%mod;
printf("%d",ans_);
return ;
}
上一篇:自动化测试基础篇--Selenium简单的163邮箱登录实例


下一篇:node.js及npm安装&配置