結果

問題 No.1112 冥界の音楽
コンテスト
ユーザー Drice
提出日時 2020-07-10 22:19:24
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 19 ms / 2,000 ms
コード長 1,688 bytes
コンパイル時間 382 ms
コンパイル使用メモリ 33,664 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-11 09:35:29
合計ジャッジ時間 1,499 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<cstdio>
const long long mod = 1e9+7;
long long a[50][50], res[50][50], c[50][50];
long long org[50], ans[50];

void mul(long long u[50][50],long long v[50][50],int n){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            c[i][j] = 0;
            for(int k = 1; k <= n; k++){
                c[i][j] += u[i][k]*v[k][j]%mod;
                if(c[i][j]>=mod) c[i][j] -= mod; 
            }
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++) u[i][j] = c[i][j];
    }
}

void power(long long u[50][50],long long b,int n){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++) res[i][j] = i==j;
    }
    while(b){
        if(b&1) mul(res,u,n);
        mul(u,u,n);
        b /= 2;
    }
}

int main(){
    int k,m; long long n;
    scanf("%d%d%lld",&k,&m,&n);
    for(int i = 0; i < m; i++){
        int p,q,r;
        scanf("%d%d%d",&p,&q,&r);
        int from = p*k+q, to = q*k+r;
        a[to][from] = 1;
        if(p==1){ 
            //printf("to = %d\n",to);
            org[to] = 1;
        }
    }
    n -= 3;
    int total = (k+1)*k;
    power(a,n,total);
    /*for(int i = 1; i <= total; i++){
        for(int j = 1; j <= total; j++) printf("%lld ",res[i][j]);
        printf("\n");
    }*/
    for(int i = 1; i <= total; i++){
        long long cur = 0;
        for(int j = 1; j <= total; j++){
            cur += org[j]*res[i][j]%mod;
            if(cur>=mod) cur -= mod;
        }
        ans[i] = cur;
    }
    long long sum = 0;
    for(int i = 1; i <= k; i++){
        int id = i*k+1;
        sum += ans[id];
        if(sum>=mod) sum -= mod;
    }
    printf("%lld\n",sum);
    return 0;
}
0