BZOJ1898: [Zjoi2004]Swamp 沼泽鳄鱼【矩阵乘法】

如果没有鳄鱼的话。就是求邻接矩阵的k次幂了。

有鳄鱼的话。比如在第i个时刻第j个点上有鳄鱼。那么把第i-1时刻的矩阵中[1..n][j]置零，第i时刻的矩阵中[j][1..n]置零。很好想通。

注意到T=2、3、4。lcm是12。那么整个周期就是12。K/12的用快速幂。K%12的暴力求。

 

?
BZOJ1898
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,s,e,k,nf,fb[52][52]={0},p[52];
struct mtx{
    int num[52][52];
    mtx(){  memset(num,0,sizeof(num));}
}M[12],org;
mtx mul(mtx a,mtx b){
    mtx c;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            for(int k=0;k<n;k++)
                c.num[i][j]=(c.num[i][j]+a.num[i][k]*b.num[k][j])%10000;
    return c;
}mtx pow(mtx a,int b){
    mtx c;
    for(int i=0;i<n;i++) c.num[i][i]=1;
    while(b){
        if(b&1) c=mul(c,a);
        b>>=1;
        a=mul(a,a);
    }return c;
}inline void clear1(int x,int y){
    for(int i=0;i<n;i++) M[x].num[y][i]=0;
}inline void clear2(int x,int y){
    for(int i=0;i<n;i++) M[x].num[i][y]=0;
}int main(){
    scanf("%d%d%d%d%d",&n,&m,&s,&e,&k);
    int x,y,t;
    for(int i=0;i<m;i++){
        scanf("%d%d",&x,&y);
        for(int j=0;j<12;j++)    M[j].num[x][y]=M[j].num[y][x]=1;
    }scanf("%d",&nf);
    for(int i=0;i<nf;i++){
        scanf("%d",&t);
        for(int j=0;j<t;j++) scanf("%d",&p[j]);
        for(int j=0;j<12;j++)    fb[j][p[j%t]]=1;
    }for(int j=0;j<12;j++)
        for(int i=0;i<n;i++) if(fb[j][i])    clear1(j,i),clear2((j+11)%12,i);
    for(int i=1;i<12;i++)    M[i]=mul(M[i-1],M[i]);
    if(k%12)    cout << mul(pow(M[11],k/12),M[k%12-1]).num[s][e] << endl;
    else        cout << pow(M[11],k/12).num[s][e] << endl;
    return 0;
}
 

BZOJ BZOJ 矩阵乘法 Comments(0) 2013年8月17日 12:26

BZOJ1297: [SCOI2009]迷路【矩阵优化】

n个顶点的有向图，每条边的边权都在1~9。问从1到n的长度为t的路径有几条。

看时间10^9立即想到矩乘。而且n≤10，边权范围只有9。那么把每个点都拆成9个。构造01矩阵。

一个点拆成9个之后这9个点首先要连通。然后就是(u,v,w)的边，从(u,w)连一条边到(v,1)，最后答案就是Matrix[1][(n,1)]。

复杂度：O(81*n^3*log(t))。rank5、、呵呵、、还不慢、、

?
BZOJ1297
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define pos(x,y) (9*((x)-1)+y)
struct matrix{
    int r,c,num[95][95];
    matrix(){memset(num,0,sizeof(num));};
    matrix(int _r,int _c):r(_r),c(_c){memset(num,0,sizeof(num));};
    inline void setone(){   for(int i=1;i<=r;i++)   num[i][i]=1;}
    matrix operator * (matrix b)const{
        matrix d(r,b.c);    for(int i=1;i<=r;i++)   for(int j=1;j<=b.c;j++){
            for(int k=1;k<=c;k++)   d.num[i][j]+=num[i][k]*b.num[k][j];
            d.num[i][j]%=2009;
        }return d;
    }
}A; int n,t;    char s[12];
matrix operator ^(matrix a,int b){
    matrix d(a.r,a.c);  d.setone();
    while(b){   if(b&1) d=d*a;  b>>=1;  a=a*a;} return d;
}int main(){
    scanf("%d%d",&n,&t);    A.r=A.c=9*n;
    for(int i=1;i<=n;i++)   for(int j=1;j<=8;j++)   A.num[pos(i,j)][pos(i,j+1)]=1;
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        for(int j=1;j<=n;j++)   if(s[j]-'0')    A.num[pos(i,s[j]-'0')][pos(j,1)]=1;
    }printf("%d\n",(A^t).num[1][pos(n,1)]);
    return 0;
}

BZOJ 矩阵乘法 bzoj Comments(0) 2013年6月07日 11:32