icpc.me 17401 - CyberFlower Algorithm

https://www.acmicpc.net/problem/17401

숭고한 공식 풀이는 여기서 보실 수 있습니다.

행렬곱 문제입니다. $n^k$을 구하는 알고리즘 중 log(k)의 복잡도로 구할 수 있는 방법을 안다면, 같은 방식으로 행렬의 거듭제곱도 nmlog(k) 의 방식으로 구할 수 있습니다.(n,m은 행렬의 크기)

모든 노드 x,y에 대하여 x에서 y로 가는 경우의 수는 행렬곱으로 표현한 것과 일치합니다. x에서 k를 들렀다가 k에서 y로 가는 모든 경로의 수의 합이기 때문이죠.

주의해야 할 점은, 행렬을 곱하는 순서를 바꾸면 답이 달라집니다. 행렬곱은 교환법칙이 성립하지 않기 때문입니다.

행렬곱 문제가 나올때마다 시간이 되면 깔끔하게 클래스로 정리해야지 하고 마음은 먹는데 쉽지 않네요…ㅜㅜ 언젠가 클래스로 정리하게 된다면 수정하여 다시 올리겠습니다.

#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
typedef long long ll;
typedef vector<vector<ll>> matrix;
matrix operator * (const matrix &a, const matrix &b) {
    int n = a.size();
    matrix c(n, vector<ll>(n));
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            for (int k=0; k<n; k++) {
                c[i][j] = (c[i][j]+a[i][k]*b[k][j])%MOD;
            }
        }
    }
    return c;
}
matrix pow(matrix a, int k){
	int n=a.size();
	matrix ans(n,vector<ll>(n));
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			ans[i][j]=(i==j?1:0);
		}
	}
	while(k){
		if(k%2) ans=ans*a;
		a=a*a;
		k>>=1;
	}
	return ans;
}
int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	int t,n,d; cin>>t>>n>>d;
	vector<matrix> arr(t,matrix(n,vector<ll>(n)));
	for(int i=0;i<t;i++){
		int m; cin>>m;
		for(int j=0;j<m;j++){
			int x,y; ll z; cin>>x>>y>>z;
			x--; y--;
			arr[i][x][y]=z;
		}
	}
	matrix ans(n,vector<ll>(n));
	matrix period(n,vector<ll>(n));
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			ans[i][j]=(i==j?1:0);
			period[i][j]=(i==j?1:0);
		}
	}
	for(int i=0;i<t;i++) period=period*arr[i];
	ans=ans*pow(period,d/t);
	for(int i=0;i<d%t;i++) ans=ans*arr[i];
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++) cout<<ans[i][j]<<" ";
		cout<<'\n';
	}
	return 0;
}

백준 17401 일하는 세포