結果
問題 | No.840 ほむほむほむら |
ユーザー |
|
提出日時 | 2019-06-14 23:10:22 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 531 ms / 4,000 ms |
コード長 | 1,581 bytes |
コンパイル時間 | 652 ms |
コンパイル使用メモリ | 116,144 KB |
実行使用メモリ | 7,364 KB |
最終ジャッジ日時 | 2024-06-22 01:44:49 |
合計ジャッジ時間 | 4,186 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop, core.stdc.string; immutable long MOD = 998244353 ; void main() { auto s = readln.split.map!(to!int); auto N = s[0]; auto K = s[1]; auto M = K ^^ 3; auto mat = new long[][](M, M); foreach (mask; 0..M) { int c = mask % K; int b = mask / K % K; int a = mask / K / K; int na = (a + 1) % K; int nb = (b + a) % K; int nc = (c + b) % K; int x = na * K^^2 + b * K + c; int y = a * K^^2 + nb * K + c; int z = a * K^^2 + b * K + nc; mat[x][mask] += 1; mat[y][mask] += 1; mat[z][mask] += 1; } long ans = 0; auto nmat = matpow(M, N, mat); foreach (mask; 0..M) if (mask % K == 0) ans = (ans + nmat[mask][0]) % MOD; ans.writeln; } long[][] matmul(int N, long[][] m1, long[][] m2) { auto ret = new long[][](N, N); foreach (i; 0..N) { foreach (j; 0..N) { ret[i][j] = 0; foreach (k; 0..N) { (ret[i][j] += m1[i][k] * m2[k][j] % MOD) %= MOD; } } } return ret; } long[][] matpow(int N, long K, long[][] mat) { auto ret = new long[][](N, N); foreach (i; 0..N) foreach (j; 0..N) ret[i][j] = i == j ? 1 : 0; while (K > 0) { if (K % 2 == 1) ret = matmul(N, ret, mat); mat = matmul(N, mat, mat); K /= 2; } return ret; }