結果

問題 No.444 旨味の相乗効果
ユーザー hermione17
提出日時 2016-11-11 23:53:44
言語 Java
(openjdk 23)
結果
AC  
実行時間 953 ms / 2,500 ms
コード長 1,579 bytes
コンパイル時間 4,134 ms
コンパイル使用メモリ 78,284 KB
実行使用メモリ 46,964 KB
最終ジャッジ日時 2024-11-25 10:07:23
合計ジャッジ時間 17,777 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.io.PrintStream;
import java.util.Scanner;
public class Y444 {
    Scanner in = new Scanner(System.in);
    PrintStream out = new PrintStream(System.out);
    long MOD = 1000000007;
    
    
    Y444() throws Exception {
        int n = in.nextInt();
        long c = in.nextLong();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        
        Matrix m = new Matrix();
        for (int i = 0; i < n; i++) {
            m.a[i][i] = a[i];
            m.a[i+n][i+n] = a[i];
            for (int j = 0; j < i; j++) {
                m.a[i+n][j] = a[i];
                m.a[i+n][j+n] = a[i];
            }
        }
                
        Matrix power = m.pow(c - 1);
        long ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ans = (ans + a[j] * power.a[i+n][j]) % MOD;
            }
        }
        power=m.mul(m);
        out.println(ans);
    }
    public static void main(String argv[]) throws Exception {
        new Y444();
    }
    
    
    class Matrix {
        long[][] a = new long[160][160];
        Matrix mul(Matrix that) {
            Matrix ret = new Matrix();
            for (int i = 0; i < a.length; i++) {
                for (int j = 0; j < a.length; j++) {
                    for (int k = 0; k < a.length; k++) {
                        ret.a[i][k] = (ret.a[i][k] + a[i][j] * that.a[j][k]);
                    }
                    
                    if ((j & 7) == 7) {
                        for (int k = 0; k < a.length; k++) {
                            ret.a[i][k] %= MOD;
                        }
                    }
                }
            }
            return ret;
        }
        Matrix pow(long p) {
            Matrix ret = new Matrix();
            Matrix x = this;
            
            for (int i = 0; i < a.length; i++) {
                ret.a[i][i] = 1;
            }
            
            while (p > 0) {
                if ((p & 1) == 1) {
                    ret = x.mul(ret);
                }
                x = x.mul(x);
                p >>= 1;
            }
            
            return ret;
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0