P2233 公交车路线

传送门

矩阵

回忆一下，矩阵式怎么运算的

$$\left[ \begin{matrix} 1 & 3 \\ 2 & 2 \\ \end{matrix} \right]\times \left[ \begin{matrix} 2 & 4 & 3 \\ 3 & 2 & 1 \\ \end{matrix} \right]= \left[ \begin{matrix} 11 & 10 & 6 \\ 10 & 12 & 8 \\ \end{matrix} \right]$$

形状上：2*2 和 2*3 的矩阵乘积后,结果是 2*3 的矩阵。

即 a*b 矩阵 和 c*d 的矩阵乘积结果是 a*d 的矩阵。其中 b 和 c 必须相等。原因看下面。

运算法则：对于结果矩阵的第 i 行第 j 列的位置的结果是由前一个矩阵的对应的行。和后一个矩阵对应的列。对应位置乘积和获得的。
    
比如第 1 行第 1 列的 11.是由前矩阵的第一行 (1,3) 和后矩阵的第一列 (2,3) 对应位置乘积和。
    
1*2 + 3*3 = 11 获得的。
    
如果上述 b 和 c 如果不相等。那么会有地方"失配"没有数值可以进行计算。不符合矩阵乘法定义。

分析

发现车站组成了一个环，所以显然可以用矩阵，并且，一个车站只能到相邻两个车站，可以列出矩阵：

$$\left( \begin{matrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end{matrix} \right)$$

但是，题中有这样一句话：

注意 tiger 一旦到达公交站 E，他不会愚蠢到再去换车。

所以到了E就不能动了,所以矩阵改为如下模样：

$$\left( \begin{matrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end{matrix} \right)$$

套矩阵快速幂求解即可。

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<cctype>
#include<queue>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
long long r_r(){
  long long x=0,f=1;
  char c=getchar();
  while(!isdigit(c)){
    if(c=='-')f=-1;
    c=getchar();
  }
  while(isdigit(c)){
    x=(x<<1)+(x<<3)+(c^48);
    c=getchar();
  }
  return x*f;
}
const int o_o=1001;
long long x[o_o][o_o];//辅助矩阵 
long long a_s[o_o][o_o];//答案矩阵 
long long x_x[o_o][o_o];//临时矩阵 
long long n,k;
const int m_d=1000;
void k_m(long long n,long long k){//矩阵快速幂 
  while(k){
    if(k&1){//更新答案矩阵 
      for(int i=1;i<=n;i++)//将答案矩阵存入临时矩阵 
        for(int j=1;j<=n;j++){
          x_x[i][j]=a_s[i][j];
          a_s[i][j]=0;//重置答案矩阵 
        }
      for(int i=1;i<=n;i++)//枚举答案矩阵和辅助矩阵（第一个矩阵）的行 
        for(int j=1;j<=n;j++)//枚举答案矩阵的行的第几个数（列）和临时矩阵（第二个矩阵）的列 
          for(int k=1;k<=n;k++)//枚举辅助矩阵（第一个矩阵）的列和临时矩阵（第二个矩阵）的行 
            a_s[i][j]=(a_s[i][j]+(x[i][k]*x_x[k][j])%m_d)%m_d;//存入答案矩阵 
    }
    //更新辅助矩阵 
    for(int i=1;i<=n;i++)//将辅助矩阵存入临时矩阵
      for(int j=1;j<=n;j++){
        x_x[i][j]=x[i][j];
        x[i][j]=0;//重置辅助矩阵 
      }
    for(int i=1;i<=n;i++)//枚举辅助矩阵和临时矩阵（第一个矩阵）的行 
      for(int j=1;j<=n;j++)//枚举辅助矩阵的行和临时矩阵（第二个矩阵）的列 
        for(int k=1;k<=n;k++)//枚举临时矩阵（第一个矩阵）的列和临时矩阵（第二个矩阵）的行 
          x[i][j]=(x[i][j]+(x_x[i][k]*x_x[k][j])%m_d)%m_d;//存入辅助矩阵 
    k>>=1;
  }
}
void yv(){
  a_s[1][8]=a_s[1][2]=1;
  a_s[2][1]=a_s[2][3]=1;
  a_s[3][2]=a_s[3][4]=1;
  a_s[4][3]=a_s[4][5]=1;
  a_s[6][5]=a_s[6][7]=1;
  a_s[7][6]=a_s[7][8]=1;
  a_s[8][7]=a_s[8][1]=1;
  x[1][8]=x[1][2]=1;
  x[2][1]=x[2][3]=1;
  x[3][2]=x[3][4]=1;
  x[4][3]=x[4][5]=1;
  x[6][5]=x[6][7]=1;
  x[7][6]=x[7][8]=1;
  x[8][7]=x[8][1]=1;
}
int main(){
  k=r_r();//读入幂 
  n=8;//矩阵大小 
  yv();//初始化矩阵 
  k_m(n,k-1);//矩阵快速幂 
  printf("%lld ",a_s[1][5]%m_d);//是哪个车站输出那个（E==5）

//  完整矩阵 
//  for(int i=1;i<=n;i++){
//    for(int j=1;j<=n;j++){
//      cout<<a_s[i][j]<<" ";
//    }
//    cout<<endl;
//  } 
  
  return 0;
}