結果

問題 No.444 旨味の相乗効果
コンテスト
ユーザー vjudge1
提出日時 2024-12-22 15:33:00
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 126 ms / 2,500 ms
コード長 1,693 bytes
コンパイル時間 1,633 ms
コンパイル使用メモリ 168,328 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-12-22 15:33:04
合計ジャッジ時間 3,099 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define int long long
using namespace std;
 
void file_IO(){
    freopen("spice.in", "r", stdin);
    freopen("spice.out", "w", stdout);
}
 
const int N = 85;
const int MOD = 1e9 + 7;
int n, c, ans = 0, v[N];
 
int fp(int x, int y){
    int res = 1;
    while (y){
        if (y & 1)  res = res * x % MOD;
        x = x * x % MOD, y >>= 1;
    }
    return res;
}
void add(int &x, int y){
    x = (x + y >= MOD ? x + y - MOD : x + y);
}
void sub(int &x, int y){
    x = (x >= y ? x - y : x + MOD - y);
}
 
struct matrix{
    int a[N][N];
    matrix(){
        memset(a, 0, sizeof(a));
    }
    matrix operator * (const matrix& b) const{
        matrix c;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                for (int k = 1; k <= n; k++)
                    add(c.a[i][j], a[i][k] * b.a[k][j] % MOD);
        return c;
    }
    void print(){
        cout << "Size: " << n << " * " << n << endl;
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= n; j++)
                cout << a[i][j] << " " ;
            cout << endl;
        }
    }
}res, base;
 
void calc(int x){
    while (x){
        if (x & 1)  res = res * base;
        base = base * base, x >>= 1;
    }
}
 
signed main(){
    //file_IO();
    cin >> n >> c;
    for (int i = 1; i <= n; i++) cin >> v[i];
    for (int i = 1; i <= n; i++) res.a[1][i] = v[i];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            base.a[i][j] = (i <= j ? v[j] : 0);
    calc(c - 1);
    for (int i = 1; i <= n; i++) add(ans, res.a[1][i]);
    for (int i = 1; i <= n; i++) sub(ans, fp(v[i], c));
    cout << ans << endl;
    return 0;
}
0