• 欢迎光临~

# Different Pass a Ports(矩阵快速幂板子)

## AC代码

``````#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define ll long long
using namespace std;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
struct matrix
{
static const int n=110;
int M[n][n];
int N;
matrix(int num)
{
N=num;
memset(M,0,sizeof(M));
}
void build(){//把一个新的矩阵构造成单位阵
for(int i=1;i<=N;i++)M[i][i]=1;
}
int *operator[](int i){//直接取出该位置的值，就不用每次都要调用M
return M[i];
}
matrix operator*(matrix&a)
{
matrix temp(N);
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
for(int k=1;k<=N;k++)
temp[i][j]=(temp[i][j]+(1LL*M[i][k]*a[k][j])%mod)%mod;
return temp;
}
matrix operator^(long long P)//矩阵快速幂
{
matrix res(N);res.build();
matrix A=*this;
while(P>0){
if(P&1)
res=res*A;
A=A*A;
P>>=1;
}
return res;
}
};
int main(void)
{
int N,M,K;scanf("%d %d %d",&N,&M,&K);
matrix res(N);
for(int i=0;i<M;i++)
{
int x,y;scanf("%d %d",&x,&y);
res[x][y]++;
res[y][x]++;
}
ll ans=0;
res=res^K;
for(int j=1;j<=N;j++)
ans=(ans+res[1][j])%mod;
cout<<ans<<endl;
return 0;
}
``````

## AC代码

``````#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn=110;
const int INF=0x3f3f3f3f;
const int mod=2017;
struct matrix
{
static const int n=maxn;
ll M[n][n];
int N;
matrix(int num)
{
N=num;
memset(M,0,sizeof(M));
}
void build(){
for(int i=1;i<=N;i++)M[i][i]=1;
}
ll* operator[](int i){
return M[i];
}
matrix operator*(matrix &a)
{
matrix temp(N);
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
for(int k=1;k<=N;k++)
temp[i][j]=(temp[i][j]+(1LL*M[i][k]*a[k][j])%mod)%mod;
return temp;
}
matrix operator^(ll P)
{
matrix res(N);res.build();
matrix A=*this;
while(P>0){
if(P&1)
res=res*A;
A=A*A;
P>>=1;
}
return res;
}
};
int main(void)
{
int N,M,K;
scanf("%d %d",&N,&M);
matrix res(N+1);res.build();//题目中有呆着原地这个选项，如果没有的话就不用
for(int i=0;i<M;i++)
{
int x,y;
scanf("%d %d",&x,&y);
res[x][y]++;//可能存在多条相同的路
res[y][x]++;
}
for(int i=1;i<=N;i++)res[i][N+1]++;//爆炸的情况,N+1为爆炸那个位置
scanf("%d",&K);
res=res^K;
ll ans=0;
for(int j=1;j<=N+1;j++)ans+=res[1][j];
cout<<ans%mod<<endl;
return 0;
}
``````