結果
問題 | No.1847 Good Sequence |
ユーザー | 👑 ygussany |
提出日時 | 2022-02-18 23:19:50 |
言語 | C (gcc 12.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,685 bytes |
コンパイル時間 | 1,286 ms |
コンパイル使用メモリ | 31,232 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-29 09:52:50 |
合計ジャッジ時間 | 2,370 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
5,248 KB |
testcase_01 | AC | 47 ms
5,376 KB |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | AC | 11 ms
5,376 KB |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | AC | 47 ms
5,376 KB |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | AC | 43 ms
5,376 KB |
testcase_24 | AC | 49 ms
5,376 KB |
testcase_25 | WA | - |
testcase_26 | AC | 47 ms
5,376 KB |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | AC | 50 ms
5,376 KB |
testcase_35 | AC | 47 ms
5,376 KB |
testcase_36 | WA | - |
testcase_37 | AC | 46 ms
5,376 KB |
testcase_38 | AC | 2 ms
5,376 KB |
testcase_39 | AC | 3 ms
5,376 KB |
testcase_40 | AC | 45 ms
5,376 KB |
ソースコード
#include <stdio.h>#define DIM 70const int Mod = 1000000007;void copy_matrix(int d, long long A[][DIM], long long B[][DIM]){int i, j;for (i = 0; i < d; i++) for (j = 0; j < d; j++) B[i][j] = A[i][j];}void prod_matrix(int d, long long A[][DIM], long long B[][DIM], long long C[][DIM]){int i, j, k;for (i = 0; i < d; i++) {for (j = 0; j < d; j++) {for (k = 0, C[i][j] = 0; k < d; k++) C[i][j] += A[i][k] * B[k][j] % Mod;C[i][j] %= Mod;}}}void pow_matrix(int d, long long A[][DIM], long long k, long long B[][DIM]){int i, j;long long C[2][DIM][DIM], D[DIM][DIM];copy_matrix(d, A, C[0]);for (i = 0; i < d; i++) for (j = 0; j < d; j++) B[i][j] = 0;for (i = 0; i < d; i++) B[i][i] = 1;for (i = 0, j = 1; k > 0; i ^= 1, j ^= 1, k >>= 1) {prod_matrix(d, C[i], C[i], C[j]);if (k % 2 == 1) {prod_matrix(d, B, C[i], D);copy_matrix(d, D, B);}}}int main(){long long L;int i, N, M, K, flag[11] = {};scanf("%lld %d %d", &L, &N, &M);for (i = 1; i <= M; i++) {scanf("%d", &K);flag[K] = 1;}int j, k, ii, jj;long long A[DIM][DIM] = {}, B[DIM][DIM];for (i = 1, j = 1; j <= N; j++, i += j) A[i][0] = 1;for (i = 1, j = 1, k = 1; 1; i++, k++) {if (k > j + 1) {j++;k = 1;if (j > N) break;}if (k != j) {for (ii = 1, jj = 1; jj <= N; jj++, ii += jj) if (jj != j) A[ii][i] = 1;} else A[DIM-1][i] = N - 1;if (k <= j) A[i+1][i] = 1;else A[i][i] = 1;}A[DIM-1][DIM-1] = N;long long ans = 0;pow_matrix(DIM, A, L, B);for (i = 1, j = 1, ans = B[DIM-1][0]; j <= N; j++, i += j + 1) if (flag[j] != 0) ans += B[i][0];printf("%lld\n", ans % Mod);fflush(stdout);return 0;}