結果
問題 | No.1050 Zero (Maximum) |
ユーザー |
![]() |
提出日時 | 2020-05-08 21:36:42 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 8 ms / 2,000 ms |
コード長 | 893 bytes |
コンパイル時間 | 215 ms |
コンパイル使用メモリ | 34,176 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-04 00:08:45 |
合計ジャッジ時間 | 889 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 |
ソースコード
#include <stdio.h>#include <stdint.h>#include <string.h>int ri() {int n;scanf("%d", &n);return n;}#define MOD 1000000007int main() {int m = ri();int k = ri();int vec[m] = { 0 };vec[0] = 1;int mat[m][m];memset(mat, 0, sizeof(mat));for (int i = 0; i < m; i++) {for (int j = 0; j < m; j++) {mat[i][(i + j) % m]++;mat[i][(int64_t) i * j % m]++;}}for (; k; k >>= 1) {if (k & 1) {int next[m] = { 0 };for (int i = 0; i < m; i++) for (int j = 0; j < m; j++)next[j] = (next[j] + (int64_t) vec[i] * mat[i][j]) % MOD;memcpy(vec, next, sizeof(next));}int next[m][m];memset(next, 0, sizeof(next));for (int i = 0; i < m; i++) for (int j = 0; j < m; j++) for (int k = 0; k < m; k++)next[i][k] = (next[i][k] + (int64_t) mat[i][j] * mat[j][k]) % MOD;memcpy(mat, next, sizeof(next));}printf("%d\n", vec[0]);return 0;}