洛谷-4159 [SCOI2009]迷路

題目描述

windy在有向圖中迷路了。 該有向圖有 N 個節點，windy從節點 0 出發，他必須恰好在 T 時刻到達節點 N-1。 現在給出該有向圖，你能告訴windy總共有多少種不同的路徑嗎？ 注意：windy不能在某個節點逗留，且通過某有向邊的時間嚴格為給定的時間。

輸入格式

第一行包含兩個整數，N T。 接下來有 N 行，每行一個長度為 N 的字元串。 第i行第j列為’0’表示從節點i到節點j沒有邊。 為’1’到’9’表示從節點i到節點j需要耗費的時間。

輸出格式

包含一個整數，可能的路徑數，這個數可能很大，隻需輸出這個數除以2009的餘數。

輸入輸出樣例

輸入 #1

2 2

11

00

輸出 #1

1

輸入 #2

5 30

12045

07105

47805

12024

12345

輸出 #2

852

說明/提示

【樣例解釋一】

0->0->1

【資料範圍】

30%的資料，滿足 2 <= N <= 5 ； 1 <= T <= 30 。

100%的資料，滿足 2 <= N <= 10 ； 1 <= T <= 1000000000 。

解釋：如果邊都是1的話，很簡單，是以我們就想辦法把它轉行成邊為1，我們對每個點進行擴充到9個，這樣的話，每條邊長為1，得到矩陣後直接矩陣快速幂即可。

#include<iostream>
#include<cstring>
#include<cstdio>
#define N 120
#define mod 2009
#define ll int
using namespace std;
int G[N][N]={0};
int n=0,T=0;
int m=0;
char str[123];
class Matrix{
    public:
        ll a[N][N],n;
        Matrix(int _n){
            n=_n;
            memset(a,0,sizeof(a));
            for(int i=1;i<=n;i++) a[i][i]=1%mod;
        }
        int get(int x,int y){
            return a[x][y];
        }
        void set(int x,int y,int val){
            a[x][y]=val%mod;
        }
        void mul(Matrix &b){
            int c[N][N]={0};
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    for(int k=1;k<=n;k++){
                        c[i][j]+=a[i][k]*b.a[k][j]%mod;
                        c[i][j]%=mod;
                    }
                }
            }
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++) a[i][j]=c[i][j];
        }
        void pow(ll k){
            Matrix ret(n);
            while(k){
                if(k&1){
                    ret.mul(*this);
                }k>>=1;
                this->mul(*this);
            }
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++) a[i][j]=ret.a[i][j]%mod;
        }
        void display(){
            for(int i=1;i<=n;i++){
                printf("%d",a[i][1]);
                for(int j=2;j<=n;j++){
                    printf(" %d",a[i][j]);
                }
                printf("\n");
            }
        }
};
int main(){
    cin>>n>>T;
    m=n*9;
    Matrix mk(m);
    for(int i=1;i<=n;i++){
        cin>>(str+1);
        for(int j=1;j<=n;j++){
            int pos=(i-1)*9+1;
            int y=str[j]-'0';
            if(y<1) continue;
            for(int k=2;k<=y;k++){
                G[pos][pos+1]=1;
                pos++;
            }
            G[pos][(j-1)*9+1]=1;
        }
    }
    for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) mk.a[i][j]=G[i][j];
    mk.pow(T);
    cout<<mk.a[1][(n-1)*9+1]<<endl;
    return 0;
}