結果

問題 No.213 素数サイコロと合成数サイコロ (3-Easy)
ユーザー akakimidoriakakimidori
提出日時 2019-06-27 13:44:45
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 320 ms / 3,000 ms
コード長 2,001 bytes
コンパイル時間 723 ms
コンパイル使用メモリ 31,752 KB
実行使用メモリ 4,376 KB
最終ジャッジ日時 2023-09-10 04:44:13
合計ジャッジ時間 2,053 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 125 ms
4,376 KB
testcase_01 AC 320 ms
4,376 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;

const i32 mod = 1000000007;

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

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, n * n * sizeof (i32));
  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, n * n * sizeof (i32));
}

#define POS(i, j) ((i) * (m + 1) + (j))

void run (void) {
  i64 n;
  i32 p, c;
  scanf ("%" SCNi64 "%" SCNi32 "%" SCNi32, &n, &p, &c);
  i32 prime[6] = {2, 3, 5, 7, 11, 13};
  i32 compo[6] = {4, 6, 8, 9, 10, 12};
  i32 m = p * 13 + c * 12;
  i32 *dp = ALLOC ((p + c + 1) * (m + 1), i32);
  dp[POS(0, 0)] = 1;
  for (i32 i = 0; i < 6; ++i) {
    i32 x = prime[i];
    for (i32 j = 0; j < p; ++j) {
      for (i32 k = 0; k <= m - x; ++k) {
        i32 y = k + x;
        dp[POS(j + 1, y)] = (dp[POS(j + 1, y)] + dp[POS(j, k)]) % mod;
      }
    }
  }
  dp += p * (m + 1);
  for (i32 i = 0; i < 6; ++i) {
    i32 x = compo[i];
    for (i32 j = 0; j < c; ++j) {
      for (i32 k = 0; k <= m - x; ++k) {
        i32 y = k + x;
        dp[POS(j + 1, y)] = (dp[POS(j + 1, y)] + dp[POS(j, k)]) % mod;
      }
    }
  }
  dp += c * (m + 1);
  i32 *t = ALLOC (m * m, i32);
  i32 *s = ALLOC (m * m, i32);
  for (i32 i = 0; i < m; ++i) {
    t[i * m + i] = 1;
  }
  for (i32 i = 0; i < m - 1; ++i) {
    s[i * m + i + 1] = 1;
  }
  for (i32 i = 1; i <= m; ++i) {
    s[(i - 1) * m + 0] = dp[i];
  }
  while (n > 0) {
    if (n & 1) matmul (t, s, t, m);
    matmul (s, s, s, m);
    n >>= 1;
  }
  i64 ans = 0;
  for (i32 i = 0; i < m; ++i) {
    ans += t[i * m + 0];
  }
  ans %= mod;
  printf ("%" PRIi64 "\n", ans);
}

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