結果
問題 | No.621 3 x N グリッド上のドミノの置き方の数 |
ユーザー |
|
提出日時 | 2017-12-25 03:49:56 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 181 ms / 3,000 ms |
コード長 | 2,481 bytes |
コンパイル時間 | 2,507 ms |
コンパイル使用メモリ | 85,536 KB |
実行使用メモリ | 54,664 KB |
最終ジャッジ日時 | 2024-12-17 18:52:46 |
合計ジャッジ時間 | 16,347 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 66 |
ソースコード
import java.util.Arrays;import java.util.Scanner;class Main {int pow(int a, int n) {return (int) Math.pow(a, n);}int at(int a, int pos) {return a / pow(3, pos) % 3;}final long MOD = 1_000_000_000 + 7;long[][] mul(long[][] a, long[][] b) {long[][] ret = new long[a.length][b[0].length];for (int i = 0; i < a.length; ++i) {for (int j = 0; j < b[i].length; ++j) {for (int k = 0; k < a[i].length; ++k) {ret[i][j] += a[i][k] * b[k][j] % MOD;ret[i][j] %= MOD;}}}return ret;}long[][] pow(long[][] a, long n) {long[][] ret = new long[a.length][a.length];for (int i = 0; i < ret.length; ++i)ret[i][i] = 1;for (; n > 0; n >>= 1, a = mul(a, a)) {if (n % 2 == 1) {ret = mul(ret, a);}}return ret;}void run() {Scanner sc = new Scanner(System.in);long n = sc.nextLong();long[][] mat = new long[3 * 3 * 3][3 * 3 * 3];//0:空白//1:未完成//2:完成for (int from = 0; from < 3 * 3 * 3; ++from) {in: for (int to = 0; to < 3 * 3 * 3; ++to) {int cur = to;{//未完成が前列に残っていないfor (int i = 0; i < 3; ++i) {if (at(from, i) == 1 && at(to, i) != 2) {continue in;} else if (at(from, i) == 1 && at(to, i) == 2) {cur = cur - pow(3, i);}}}if (at(cur, 0) == 2 && at(cur, 1) == 2) {cur -= pow(3, 0);cur -= pow(3, 1);}if (at(cur, 1) == 2 && at(cur, 2) == 2) {cur -= pow(3, 1);cur -= pow(3, 2);}if (at(cur, 0) == 2 || at(cur, 1) == 2 || at(cur, 2) == 2) {continue in;}{//空白が無いfor (int i = 0; i < 3; ++i) {if (at(from, i) == 0 && at(to, i) == 0)continue in;}if (at(to, 0) == 0 && at(to, 1) == 0)continue in;if (at(to, 1) == 0 && at(to, 2) == 0)continue in;if (at(from, 0) == 0 && at(from, 1) == 0)continue in;if (at(from, 1) == 0 && at(from, 2) == 0)continue in;}mat[to][from]++;}}long ans = 0;long[][] v = new long[3 * 3 * 3][1];v[3 * 3 * 3 - 1][0] = 1;v = mul(pow(mat, n), v);for (int i = 0; i < 3 * 3 * 3; ++i) {if (at(i, 0) == 1 || at(i, 1) == 1 || at(i, 2) == 1)continue;ans = (ans + v[i][0]) % MOD;}System.out.println(ans);}void tr(Object... objects) {System.out.println(Arrays.deepToString(objects));}public static void main(String[] args) {new Main().run();}}