結果
| 問題 | No.2257 Swim and Sleep |
| ユーザー |
👑  hos.lyric
|
| 提出日時 | 2023-03-24 23:34:49 |
| 言語 | D (dmd 2.109.1) |
| 結果 |
AC
|
| 実行時間 | 1,469 ms / 2,000 ms |
| コード長 | 11,900 bytes |
| コンパイル時間 | 1,748 ms |
| コンパイル使用メモリ | 159,408 KB |
| 実行使用メモリ | 188,700 KB |
| 最終ジャッジ日時 | 2024-06-22 17:41:28 |
| 合計ジャッジ時間 | 23,953 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 17 |
コンパイルメッセージ
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/numeric.d(2999): Warning: cannot inline function `std.numeric.gcdImpl!uint.gcdImpl` /home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/numeric.d(2999): Warning: cannot inline function `std.numeric.gcdImpl!ulong.gcdImpl`
ソースコード
import std.conv, std.functional, std.range, std.stdio, std.string;import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, 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(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1;(unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }struct ModInt(uint M_) {import std.conv : to;alias M = M_;uint x;this(ModInt a) { x = a.x; }this(uint x_) { x = x_ % M; }this(ulong x_) { x = cast(uint)(x_ % M); }this(int x_) { x = ((x_ %= cast(int)(M)) < 0) ? (x_ + cast(int)(M)) : x_; }this(long x_) { x = cast(uint)(((x_ %= cast(long)(M)) < 0) ? (x_ + cast(long)(M)) : x_); }ref ModInt opAssign(T)(inout(T) a) if (is(T == uint) || is(T == ulong) || is(T == int) || is(T == long)) { return this = ModInt(a); }ref ModInt opOpAssign(string op, T)(T a) {static if (is(T == ModInt)) {static if (op == "+") { x = ((x += a.x) >= M) ? (x - M) : x; }else static if (op == "-") { x = ((x -= a.x) >= M) ? (x + M) : x; }else static if (op == "*") { x = cast(uint)((cast(ulong)(x) * a.x) % M); }else static if (op == "/") { this *= a.inv(); }else static assert(false);return this;} else static if (op == "^^") {if (a < 0) return this = inv()^^(-a);ModInt b = this, c = 1U;for (long e = a; e; e >>= 1) { if (e & 1) c *= b; b *= b; }return this = c;} else {return mixin("this " ~ op ~ "= ModInt(a)");}}ModInt inv() const {uint a = M, b = x; int y = 0, z = 1;for (; b; ) { const q = a / b; const c = a - q * b; a = b; b = c; const w = y - cast(int)(q) * z; y = z; z = w; }assert(a == 1); return ModInt(y);}ModInt opUnary(string op)() const {static if (op == "+") { return this; }else static if (op == "-") { ModInt a; a.x = x ? (M - x) : 0U; return a; }else static assert(false);}ModInt opBinary(string op, T)(T a) const { return mixin("ModInt(this) " ~ op ~ "= a"); }ModInt opBinaryRight(string op, T)(T a) const { return mixin("ModInt(a) " ~ op ~ "= this"); }bool opCast(T: bool)() const { return (x != 0U); }string toString() const { return x.to!string; }}enum MO = 998244353;alias Mint = ModInt!MO;void main() {auto subete = new int[][][][][](8 + 1, 8 + 1);int[][][] sugoi;//*// debug {foreach (m; 1 .. 8 + 1) foreach (n; 1 .. 8 + 1) {// foreach (m; [4]) foreach (n; [4]) {// writefln("m = %s, n = %s", m, n);// writeln;const g = gcd(m, n);int cnt;auto a = new int[][](m, n);auto fs = new int[4][m];auto gs = new int[4][n];auto ps = new int[4][g];auto qs = new int[4][g];bool covered() {{bool ok = true;foreach (x; 0 .. m) ok = ok && (fs[x][1] == n || fs[x][3] == n);if (ok) return true;}{bool ok = true;foreach (y; 0 .. n) ok = ok && (gs[y][0] == m || gs[y][2] == m);if (ok) return true;}foreach (s; 0 .. 2) {bool ok = true;foreach (x; 0 .. m) foreach (y; 0 .. n) ok = ok && (((x + y + s) & 1) == (a[x][y] & 1));if (ok) return true;}{bool ok = true;foreach (z; 0 .. g) ok = ok && (ps[z][0] == m * n / g || ps[z][1] == m * n / g || ps[z][2] == m * n / g || ps[z][3] == m * n / g);if (ok) return true;}{bool ok = true;foreach (w; 0 .. g) ok = ok && (qs[w][0] == m * n / g || qs[w][1] == m * n / g || qs[w][2] == m * n / g || qs[w][3] == m * n / g);if (ok) return true;}return false;}void dfs(int x, int y) {if (x == m) {++cnt;auto aa = new int[][](m, n);foreach (xx; 0 .. m) foreach (yy; 0 .. n) aa[xx][yy] = a[xx][yy];subete[m][n] ~= aa;if (!covered) {/*foreach (xx; 0 .. m) {foreach (yy; 0 .. n) {write("v>^<"[a[xx][yy]]);}writeln;}writeln;*/// !assert(g % 4 == 0);foreach (xx; 0 .. m) foreach (yy; 0 .. n) {assert(a[xx][yy] == a[xx % 4][yy % 4]);}if (m == 4 && n == 4) {sugoi ~= aa;}}} else if (y == n) {dfs(x + 1, 0);} else {foreach (b; 0 .. 4) {a[x][y] = b;const z = (x + y) % g;const w = (x + (n - y)) % g;++fs[x][b];++gs[y][b];++ps[z][b];++qs[w][b];bool ok = true;ok = ok && !(fs[x][1] && fs[x][3]);ok = ok && !(gs[y][0] && gs[y][2]);ok = ok && !(ps[z][0] && ps[z][1]);ok = ok && !(ps[z][2] && ps[z][3]);ok = ok && !(qs[w][0] && qs[w][3]);ok = ok && !(qs[w][2] && qs[w][1]);if (ok) {dfs(x, y + 1);}--fs[x][b];--gs[y][b];--ps[z][b];--qs[w][b];}}}dfs(0, 0);stderr.writeln(m, " ", n, ": ", cnt);stderr.flush;// writeln('-'.repeat(80).array);// writeln;// stdout.flush;}// return;// }//*/try {for (; ; ) {const numCases = readInt;foreach (caseId; 0 .. numCases) {const M = readLong;const N = readLong;const K = readInt;auto X = new long[K];auto Y = new long[K];auto D = new long[K];foreach (k; 0 .. K) {X[k] = readInt;Y[k] = readInt;D[k] = "RULD".indexOf(readToken[0]);}const G = gcd(M, N);debug {writefln("M = %s, N = %s, G = %s", M, N, G);writeln("X = ", X);writeln("Y = ", Y);writeln("D = ", D);}int[long] fs, gs, ps, qs;foreach (k; 0 .. K) {const x = X[k];const y = Y[k];const z = (x + y) % G;const w = (x + N - y) % G;if (x !in fs) fs[x] = 0;if (y !in gs) gs[y] = 0;if (z !in ps) ps[z] = 0;if (w !in qs) qs[w] = 0;fs[x] |= 1 << D[k];gs[y] |= 1 << D[k];ps[z] |= 1 << D[k];qs[w] |= 1 << D[k];}debug {writeln("fs = ", fs);writeln("gs = ", gs);writeln("ps = ", ps);writeln("qs = ", qs);}int all;foreach (k; 0 .. K) {all |= 1 << D[k];}Mint ans;// trivial each x{bool ok = true;long m = M;foreach (x, f; fs) {ok = ok && (f == 1 << 1 || f == 1 << 3);--m;}if (ok) {debug {writefln("trivial each x: m = %s", m);}ans += Mint(2)^^m;}}// trivial each y{bool ok = true;long n = N;foreach (y, g; gs) {ok = ok && (g == 1 << 0 || g == 1 << 2);--n;}if (ok) {debug {writefln("trivial each y: n = %s", n);}ans += Mint(2)^^n;}}// 2 specialbool[2] oks;if (G % 2 == 0) {foreach (s; 0 .. 2) {bool ok = true;foreach (k; 0 .. K) {ok = ok && (((X[k] + Y[k] + s) & 1) == (D[k] & 1));}long m = M, n = N;foreach (x, f; fs) {ok = ok && !((f >> 1 & 1) && (f >> 3 & 1));if ((f >> 1 & 1) || (f >> 3 & 1)) --m;}foreach (y, g; gs) {ok = ok && !((g >> 0 & 1) && (g >> 2 & 1));if ((g >> 0 & 1) || (g >> 2 & 1)) --n;}if (ok) {debug {writefln("2 special: s = %s, m = %s, n = %s", s, m, n);}ans += Mint(2)^^(m + n);}oks[s] = ok;}}debug {writeln("oks = ", oks);}// other zforeach (i; 0 .. 2) {int d0, d1;final switch (i) {case 0: d0 = 0; d1 = 1; break;case 1: d0 = 2; d1 = 3; break;}bool ok = true;long g = G;foreach (z, p; ps) {ok = ok && (p == 1 << d0 || p == 1 << d1);--g;}if (ok) {Mint way = Mint(2)^^g;if (all == 0 || all == 1 << d0) way -= 1;if (all == 0 || all == 1 << d1) way -= 1;foreach (s; 0 .. 2) if (oks[s]) way -= 1;debug {writefln("other z: d0 = %s, d1 = %s, way = %s", d0, d1, way);}ans += way;}}// other wforeach (i; 0 .. 2) {int d0, d1;final switch (i) {case 0: d0 = 0; d1 = 3; break;case 1: d0 = 1; d1 = 2; break;}bool ok = true;long g = G;foreach (w, q; qs) {ok = ok && (q == 1 << d0 || q == 1 << d1);--g;}if (ok) {Mint way = Mint(2)^^g;if (all == 0 || all == 1 << d0) way -= 1;if (all == 0 || all == 1 << d1) way -= 1;foreach (s; 0 .. 2) if (oks[s]) way -= 1;debug {writefln("other w: d0 = %s, d1 = %s, way = %s", d0, d1, way);}ans += way;}}if (G % 4 == 0) {int[4][4] b;foreach (k; 0 .. K) {b[X[k] % 4][Y[k] % 4] |= 1 << D[k];}foreach (a; sugoi) {bool ok = true;foreach (x; 0 .. 4) foreach (y; 0 .. 4) {ok = ok && (b[x][y] == 0 || b[x][y] == 1 << a[x][y]);}if (ok) {debug {writeln("sugoi ", a);}ans += 1;}}}writeln(ans);debug {if (M <= 8 && N <= 8) {int brt;foreach (a; subete[M][N]) {bool ok = true;foreach (k; 0 .. K) {ok = ok && (a[X[k]][Y[k]] == D[k]);}if (ok) {++brt;if (M <= 4 && N <= 4) {writeln("brt ", a);}}}writeln("brt = ", brt);assert(Mint(brt) == ans);}}}}} catch (EOFException e) {}}