【题解】Luogu P2233 [HNOI2002] 公交路线矩乘加速递推

墨蓝 2023-08-17 16:49 137阅读 0赞

构造矩阵

发现只能相邻两个车站转移，所以能够写出下面这个矩阵

$\{\\begin\{bmatrix\} 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\{bmatrix\}\}$

再次读题，发现一旦到达E就不会再出来，于是把E的出边去掉

$\{\\begin\{bmatrix\} 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\{bmatrix\}\}$

对他进行n次方就是方案数

code

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 namespace gengyf{
     4 #define ll long long
     5 const int mod=1000;
     6 inline int read(){
     7     int x=0,f=1;
     8     char c=getchar();
     9     while(c<'0'||c>'9'){
         if(c=='-')f=-1;c=getchar();}
    10     while(c>='0'&&c<='9'){x=(x*10)+c-'0';c=getchar();}
    11     return x*f;
    12 }
    13 int n;
    14 struct matrix{
    15     int a[8][8];
    16     matrix(int op=0){
    17         memset(a,0,sizeof(a));
    18         if(op==1){
    19             for(int i=0;i<8;i++){
    20                 a[i][i]=1;
    21             }
    22         }
    23         if(op==2){
    24             for(int i=0;i<7;i++){
    25                 a[i][i+1]=1;a[i+1][i]=1;
    26             }
    27             a[7][0]=1;a[0][7]=1;
    28             a[4][3]=0;a[4][5]=0;
    29         }
    30     }
    31 };
    32 matrix operator*(const matrix &x,const matrix &y){
    33     matrix ans(0);
    34     for(int i=0;i<=7;i++)
    35         for(int j=0;j<=7;j++)
    36             for(int k=0;k<=7;k++){
    37                 ans.a[j][k]+=x.a[j][i]*y.a[i][k];
    38                 ans.a[j][k]%=mod;
    39             }
    40     return ans;
    41 }
    42 matrix qpow(matrix d,int n){
    43     matrix ans(1);
    44     while(n>0){
    45         if(n&1){
    46             ans=ans*d;
    47         }
    48         d=d*d;n>>=1;
    49     }
    50     return ans;
    51 }
    52 int main(){
    53     n=read();
    54     printf("%d\n",qpow(matrix(2),n).a[0][4]);
    55     return 0;
    56 }
    57 }
    58 signed main(){
    59   gengyf::main();
    60   return 0;
    61 }

转载于:https://www.cnblogs.com/gengyf/p/11599235.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230809/078d1f99d1044b0c9e946b6a715ede46.png