DZY 's BLOG

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

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

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

#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;
}

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、、呵呵、、还不慢、、

#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;
}