[TIOJ] 1428. 影分身之術

題目連結:http://tioj.infor.org/problems/1428

---

其實鄰接矩陣除了MLE外其實還有個功能，那就是你可以直接把他n次方，得到的就是任意兩點走n步有幾種走法的答案，然後n次方都可以用快速冪，所以這題其實就把圖用鄰接矩陣存起來，然後快速冪，複雜度$O(N^3 \log_2{L})$

#include <stdio.h>
#include <algorithm>
typedef long long lld;

int n,m,q,l;

auto graph = new lld[160][160];
auto temp0 = new lld[160][160];
auto temp1 = new lld[160][160];

inline void matrixTime(lld [][160],lld [][160],lld [][160]);

int main(){
	scanf("%d %d %d %d",&n,&m,&q,&l);
	for(int j=0;j<n;j++){
		for(int k=0;k<n;k++){
			graph[j][k]=(j==k)?1:0;
		}
	}
	for(int i=0;i<m;i++){
		int s,e;
		scanf("%d %d",&s,&e);
		temp0[s][e]++;
	}
	bool which=0;
	while(l){
		if(l&1){
			auto tp = new lld[160][160];
			matrixTime(graph,which?temp1:temp0,tp);
			std::swap(tp,graph);
		}
		l>>=1;
		if(which)
			matrixTime(temp1,temp1,temp0);
		else
			matrixTime(temp0,temp0,temp1);
		
		which=!which;
	}
	for(int i=0;i<q;i++){
		int x,y;
		scanf("%d %d",&x,&y);
		printf("%lld\n",graph[x][y]);
	}
	return 0;
}

inline void matrixTime(lld a[][160],lld b[][160],lld c[][160]){
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			c[i][j]=0;
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			for(int k=0;k<n;k++){
				c[i][j] += (a[i][k]*b[k][j]%1000000009);
				c[i][j] %= 1000000009;
			}
		}
	}
}