結果

問題 No.444 旨味の相乗効果
コンテスト
ユーザー akakimidori
提出日時 2019-06-13 11:11:19
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 87 ms / 2,500 ms
コード長 1,500 bytes
コンパイル時間 198 ms
コンパイル使用メモリ 31,488 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-13 05:51:00
合計ジャッジ時間 1,661 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>
#include<string.h>

typedef int32_t i32;
typedef int64_t i64;

#define ALLOC(size,type) ((type*)calloc((size),sizeof(type)))

const i32 mod = 1000000007;

void matmul (i32 *c, i32 *a, i32 *b, i32 n) {
  static i32 *tmp = NULL;
  if (tmp == NULL) {
    tmp = ALLOC (n * n, i32);
  }
  memset (tmp, 0, sizeof (i32) * n * n);
  for (i32 i = 0; i < n; ++i) {
    for (i32 k = 0; k < n; ++k) {
      for (i32 j = 0; j < n; ++j) {
        tmp[i * n + j] = (tmp[i * n + j] + (i64) a[i * n + k] * b[k * n + j]) % mod;
      }
    }
  }
  memcpy (c, tmp, sizeof (i32) * n * n);
}

i32 mod_pow (i32 r, i64 n) {
  i64 t = 1;
  i64 s = r;
  while (n > 0) {
    if (n & 1) t = t * s % mod;
    s = s * s % mod;
    n >>= 1;
  }
  return t;
}

void run (void) {
  i32 n;
  i64 c;
  scanf ("%" SCNi32 "%" SCNi64, &n, &c);
  i32 *a = ALLOC (n, i32);
  for (i32 i = 0; i < n; ++i) {
    scanf ("%" SCNi32, a + i);
  }
  i32 *t = ALLOC (n * n, i32);
  i32 *s = ALLOC (n * n, i32);
  for (i32 i = 0; i < n; ++i) {
    t[i * n + i] = 1;
  }
  for (i32 i = 0; i < n; ++i) {
    for (i32 j = 0; j <= i; ++j) {
      s[i * n + j] = a[i];
    }
  }
  i64 x = c;
  while (x > 0) {
    if (x & 1) matmul (t, s, t, n);
    matmul (s, s, s, n);
    x >>= 1;
  }
  i64 ans = 0;
  for (i32 i = 0; i < n; ++i) {
    ans += mod + t[i * n] - mod_pow (a[i], c);
  }
  ans %= mod;
  printf ("%" PRIi64 "\n", ans);
}

int main (void) {
  run();
  return 0;
}
0