結果
問題 | No.578 3 x N グリッド上のサイクルのサイズ(easy) |
ユーザー |
👑 |
提出日時 | 2019-04-27 12:51:35 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 2,812 bytes |
コンパイル時間 | 1,217 ms |
コンパイル使用メモリ | 120,948 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-22 01:03:04 |
合計ジャッジ時間 | 2,824 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
import std.conv, std.stdio, std.string;import std.algorithm, std.array, std.bigint, std.container, std.math, std.numeric, std.range, std.regex, std.typecons;import core.bitop;class EOFException : Throwable { this() { super("EOF"); } }string[] tokens;string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }int readInt() { return readToken.to!int; }long readLong() { return readToken.to!long; }real readReal() { return readToken.to!real; }bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }int binarySearch(T)(in T[] as, in bool delegate(T) test) { int low = -1, upp = cast(int)(as.length); for (; low + 1 < upp; ) { int mid = (low + upp)>> 1; (test(as[mid]) ? low : upp) = mid; } return upp; }int lowerBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a < val)); }int upperBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a <= val)); }enum MO = 10L^^9 + 7;enum V = 20;long[][] mul(long[][] a, long[][] b) {auto ret = new long[][](V, V);foreach (u; 0 .. V) foreach (w; 0 .. V) foreach (v; 0 .. V) {(ret[u][v] += a[u][w] * b[w][v]) %= MO;}return ret;}long[][] A;void add(int u, int v, int c) {enum NUM = [0, 0, 2, 2, 2, 2, 2, 2, 4, 4];A[u][v] += 1;A[u][10 + v] += (c + NUM[v]);A[10 + u][10 + v] += 1;}void main() {/*0 1 2 3 4 5 6 7 8 9- - - - -- - - - =- - - = =- - - = -*/A = new long[][](V, V);add(0, 0, 0);add(1, 1, 0);add(0, 2, 1); add(0, 3, 2); add(0, 4, 3); add(0, 5, 1); add(0, 6, 2); add(0, 7, 1);add(2, 1, 1); add(3, 1, 2); add(4, 1, 3); add(5, 1, 1); add(6, 1, 2); add(7, 1, 1);add(2, 2, 0); add(2, 3, 1); add(2, 4, 2);add(3, 2, 1); add(3, 3, 0); add(3, 4, 1); add(3, 5, 1); add(3, 6, 2);add(4, 2, 2); add(4, 3, 1); add(4, 4, 0); add(4, 5, 2); add(4, 6, 1); add(4, 7, 2);add(5, 3, 1); add(5, 4, 2); add(5, 5, 0); add(5, 6, 1);add(6, 3, 2); add(6, 4, 1); add(6, 5, 1); add(6, 6, 0); add(6, 7, 1);add(7, 4, 2); add(7, 6, 1); add(7, 7, 0);add(8, 8, 0);add(0, 8, 2); add(2, 8, 1); add(7, 8, 1);add(8, 4, 1);add(9, 9, 0);add(4, 9, 1);add(9, 1, 2); add(9, 2, 1); add(9, 7, 1);try {for (; ; ) {const N = readLong();auto a = A;auto b = new long[][](V, V);foreach (u; 0 .. V) {b[u][u] = 1;}for (long n = N + 1; n; n >>= 1) {if (n & 1) {b = mul(b, a);}a = mul(a, a);}writeln(b[0][10 + 1]);}} catch (EOFException e) {}}