矩阵bzoj1898

This article is made by Jason-Cow.
Welcome to reprint.
But please post the article's address.

BZOJ1898 Come On

图上求路径数问题

随机地加入一些“鱼”，它们的变化有周期性，且周期为2,3或4

人不可与“鱼”共处一个柱子，问从S->T恰好经过K步的方案数

很容易想到BFS，但是K太大

观察到lcm(2,3,4)=12

所以可以用矩阵存储，求出转移矩阵，然后快速幂加速

Ans=A[0]^(K/12)

然后对于剩下的K%12累乘过去

Ans=Ans*A[i]

题目里有一些板子，总结一下，可以备用

1.矩阵乘法,忽略 “ +0 ”

Matrix operator*(Matrix A,Matrix B){
  Matrix C;
  for(int k=1;k<=N;k++)
    for(int i=1;i<=N;i++)
      if(A.a[i][k])
    　　for(int j=1;j<=N;j++)
      　　if(B.a[k][j])
        　　(C.a[i][j]+=(A.a[i][k]*B.a[k][j])%MOD)%=MOD;
  return C;
}

2.矩阵快速幂，基于“ * ”

Matrix operator^(Matrix A,int b){
  Matrix ans;for(int i=1;i<=N;i++)ans.a[i][i]=1;
  for(;b;A=A*A,b>>=1)if(b&1)ans=ans*A;
  return ans;
}

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <cstdio>
 6 #include <vector>
 7 #include <cmath>
 8 #include <queue>
 9 #include <map>
10 #include <set>
11 using namespace std;
12 #define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
13 inline int _(){
14   int ans=0;char x=getchar();bool f=0;
15   while(x<'0'||x>'9'){if(x=='-')f=1;x=getchar();}
16   while(x>='0'&&x<='9')ans=ans*10+x-'0',x=getchar();
17   return f?-ans:ans;
18 }
19 const int MOD=10000,SZ=51;
20 int N,M,S,T,K,F,f[21][5],t[21];
21 struct Matrix{
22   int a[SZ][SZ];
23   Matrix(){memset(a,0,sizeof(a));}
24 }A[13],Ans;
25 Matrix operator*(Matrix A,Matrix B){
26   Matrix C;
27   for(int k=1;k<=N;k++)
28     for(int i=1;i<=N;i++)
29       if(A.a[i][k])
30     　　for(int j=1;j<=N;j++)
31       　　if(B.a[k][j])
32         　　(C.a[i][j]+=(A.a[i][k]*B.a[k][j])%MOD)%=MOD;
33   return C;
34 }
35 Matrix operator^(Matrix A,int b){
36   Matrix ans;for(int i=1;i<=N;i++)ans.a[i][i]=1;
37   for(;b;A=A*A,b>>=1)if(b&1)ans=ans*A;
38   return ans;
39 }
40 int main(){
41   N=_(),M=_(),S=_()+1,T=_()+1,K=_();
42   int i,j,k,x,y;
43   for(i=1;i<=M;i++)
44     for(x=_()+1,y=_()+1,j=1;j<=12;j++)A[j].a[x][y]=A[j].a[y][x]=1;
45 
46   for(F=_(),i=1;i<=F;i++)
47     for(j=1,t[i]=_();j<=t[i];j++)f[i][j]=_()+1;
48 
49   for(i=1;i<=F;i++)
50     for(j=1;j<=12;j++)
51       for(k=1,x=f[i][j%t[i]+1];k<=N;k++)
52     　　A[j].a[k][x]=0;
53 
54   for(i=1;i<=N ;i++)A[0].a[i][i]=1;
55   for(i=1;i<=12;i++)A[0]=A[0]*A[i];
56   Ans=A[0]^(K/12);
57   for(i=1;i<=K%12;i++)Ans=Ans*A[i];
58   printf("%d\n",Ans.a[S][T]);
59   return 0;
60 }

~~Jason_liu O(∩_∩)O