真的是假的吗?

题解 P2579 【[ZJOI2005]沼泽鳄鱼】
题目笔记

今天刚刚学习了矩阵乘法(然而全机房可能就我自己不会

看到网上说这道题是矩阵乘法的入门题,于是就来尝试

然后我肯定是不会的,于是就深入思考看题解

发现邻接矩阵做乘法有些神奇的性质

对于任意 $g[i][j]^n$ , 表示从i出发走n步恰好到j的方案数

了解了这个性质以后,这道题就肥肠明了了

但是还要考虑食人鱼的问题

我们发现食人鱼游动的周期只有 $2,3,4$ 三种

所以我们就直接处理他们的最小公共周期 $12$

我们设g[i]表示在走第 $k * 12 + i (k∈Z)$ 步的时候整个图的联通情况

然后我们就处理出每走 $12$ 步的后情况的矩阵

然后以每 $12$ 步为一个整体做快速幂

最后单独处理余下的时间即可

上代码↓

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int M = 55 ;
const int N = 15 ;
const int mod = 10000 ;
using namespace std ;
int n , m , s , t , k , Fish ;
int G[M][M] ;
struct Mat{
    int f[M][M] ;
}Ans , g[N] , b , st ;
int w[M] ;
Mat operator * (Mat A , Mat B){
    Mat temp ;
    memset(temp.f , 0 , sizeof(temp.f)) ;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
        for(int k=1;k<=n;k++)
          temp.f[i][j] = (temp.f[i][j] + A.f[i][k] * B.f[k][j])%mod ;
    return temp ;
}
inline Mat Pow(Mat Base , int k){
    Mat temp = st ;
    while(k){
        if(k&1) temp = (temp * Base) ;
        Base = (Base * Base) ; k >>= 1 ;
    }
    return temp ;
}
int main(){
    cin >> n >> m >> s >> t >> k ;
    ++s ; ++t ;
    for(int i=1;i<=n;i++) st.f[i][i] = 1 ;
    for(int i=1 , x , y;i<=m;i++){
        cin >> x >> y ;
        ++x , ++y ;
        for(int j=1;j<=12;j++) g[j].f[x][y] = g[j].f[y][x] = 1 ;
    }
    cin >> Fish ;
    while(Fish--){
        int num = 0 ; cin >> num ;
        for(int i=1;i<=num;i++)  cin >> w[i] , w[i]++ ;
        for(int i=1;i<=n;i++)
          for(int j=0;j<=12;j++)
            g[j].f[i][w[j%num + 1]] = 0 ;
    }
    for(int i=1;i<=n;i++) b.f[i][i] = 1 ;
    for(int i=1;i<=12;i++) b = (b * g[i]) ;
    Ans = Pow(b , k/12) ;
    for(int i=1;i<=k%12;i++) Ans = (Ans * g[i]) ;
    cout << Ans.f[s][t] <<endl ;
    return 0 ;
}
评论