結果

問題 No.444 旨味の相乗効果
ユーザー akakimidori
提出日時 2019-06-13 11:11:19
言語 C
(gcc 8.3.0)
結果
AC  
実行時間 76 ms
コード長 1,500 Byte
コンパイル時間 315 ms
使用メモリ 968 KB
最終ジャッジ日時 2019-08-22 23:10:55

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
00_sample1.txt AC 0 ms
968 KB
00_sample2.txt AC 0 ms
968 KB
00_sample3.txt AC 1 ms
964 KB
00_sample4.txt AC 0 ms
968 KB
00_sample5.txt AC 76 ms
968 KB
10_small1.txt AC 0 ms
964 KB
10_small2.txt AC 0 ms
964 KB
10_small3.txt AC 5 ms
968 KB
10_small4.txt AC 2 ms
968 KB
10_small5.txt AC 2 ms
964 KB
10_small6.txt AC 1 ms
964 KB
20_medium1.txt AC 1 ms
968 KB
20_medium2.txt AC 41 ms
968 KB
20_medium3.txt AC 23 ms
968 KB
20_medium4.txt AC 2 ms
968 KB
20_medium6.txt AC 1 ms
964 KB
30_large1.txt AC 75 ms
964 KB
30_large3.txt AC 1 ms
964 KB
30_large4.txt AC 1 ms
968 KB
30_large5.txt AC 12 ms
964 KB
30_large6.txt AC 72 ms
968 KB
99_corner1.txt AC 1 ms
968 KB
99_corner2.txt AC 1 ms
968 KB
99_corner3.txt AC 1 ms
964 KB
99_corner4.txt AC 3 ms
968 KB
99_corner5.txt AC 1 ms
968 KB
99_corner6.txt AC 1 ms
968 KB
system_test1.txt AC 1 ms
964 KB
テストケース一括ダウンロード

ソースコード

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