結果
| 問題 | No.310 2文字しりとり |
| ユーザー |
👑  hos.lyric
|
| 提出日時 | 2020-03-28 17:06:20 |
| 言語 | D (dmd 2.109.1) |
| 結果 |
AC
|
| 実行時間 | 2,567 ms / 6,000 ms |
| コード長 | 9,086 bytes |
| コンパイル時間 | 3,226 ms |
| コンパイル使用メモリ | 160,584 KB |
| 実行使用メモリ | 38,072 KB |
| 最終ジャッジ日時 | 2024-06-22 20:13:07 |
| 合計ジャッジ時間 | 17,664 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 28 |
ソースコード
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)); }uint xrand() {static uint x = 314159265, y = 358979323, z = 846264338, w = 327950288;uint t = x ^ x << 11; x = y; y = z; z = w; return w = w ^ w >> 19 ^ t ^ t >> 8;}int root(int[] uf, int u) {return (uf[u] < 0) ? u : (uf[u] = uf.root(uf[u]));}bool connect(int[] uf, int u, int v) {u = uf.root(u);v = uf.root(v);if (u == v) return false;if (uf[u] > uf[v]) swap(u, v);uf[u] += uf[v];uf[v] = u;return true;}F[] findLinearRecurrence(F)(F[] as) {import std.algorithm : min;const n = cast(int)(as.length);int d, m;auto cs = new F[n + 1], bs = new F[n + 1];cs[0] = bs[0] = 1;F invBef = 1;foreach (i; 0 .. n) {++m;F dif = as[i];foreach (j; 1 .. d + 1) dif += cs[j] * as[i - j];if (dif.x != 0) {auto csDup = cs.dup;const r = dif * invBef;foreach (j; m .. n) cs[j] -= r * bs[j - m];if (2 * d <= i) {d = i + 1 - d;m = 0;bs = csDup;invBef = dif.inv;}}}return cs[0 .. d + 1];}struct ModInt(int M_) {import std.conv : to;alias M = M_;int x;this(ModInt a) { x = a.x; }this(long a) { x = cast(int)(a % M); if (x < 0) x += M; }ref ModInt opAssign(long a) { return (this = ModInt(a)); }ref ModInt opOpAssign(string op)(ModInt a) {static if (op == "+") { x += a.x; if (x >= M) x -= M; }else static if (op == "-") { x -= a.x; if (x < 0) x += M; }else static if (op == "*") { x = cast(int)((cast(long)(x) * a.x) % M); }else static if (op == "/") { this *= a.inv(); }else static assert(false);return this;}ref ModInt opOpAssign(string op)(long a) {static if (op == "^^") {if (a < 0) return (this = inv()^^(-a));ModInt t2 = this, te = ModInt(1);for (long e = a; e > 0; e >>= 1) {if (e & 1) te *= t2;t2 *= t2;}x = cast(int)(te.x);return this;} else return mixin("this " ~ op ~ "= ModInt(a)");}ModInt inv() const {int a = x, b = M, y = 1, z = 0, t;for (; ; ) {t = a / b; a -= t * b;if (a == 0) {assert(b == 1 || b == -1);return ModInt(b * z);}y -= t * z;t = b / a; b -= t * a;if (b == 0) {assert(a == 1 || a == -1);return ModInt(a * y);}z -= t * y;}}ModInt opUnary(string op: "-")() const { return ModInt(-x); }ModInt opBinary(string op, T)(T a) const {return mixin("ModInt(this) " ~ op ~ "= a");}ModInt opBinaryRight(string op)(long a) const {return mixin("ModInt(a) " ~ op ~ "= this");}bool opCast(T: bool)() const { return (x != 0); }string toString() const { return x.to!string; }}enum MO = 1000000007;alias Mint = ModInt!MO;void main() {try {for (; ; ) {debug {writeln("========");}const N = readInt();const M = readInt();auto A = new int[M];auto B = new int[M];foreach (k; 0 .. M) {A[k] = readInt() - 1;B[k] = readInt() - 1;}auto adj = new bool[][](N, N);foreach (u; 0 .. N) foreach (v; 0 .. N) {adj[u][v] = true;}foreach (k; 0 .. M) {adj[A[k]][B[k]] = false;}auto used = new bool[N];auto deg = new int[N];auto uf = new int[N];uf[] = -1;foreach (u; 0 .. N) foreach (v; 0 .. N) {if (adj[u][v]) {++deg[u];--deg[v];used[u] = used[v] = true;uf.connect(u, v);}}int[] us;foreach (u; 0 .. N) {if (used[u]) {us ~= u;}}if (us.empty) {writeln(1);continue;}bool ok = true;int s = -1, t = -1;foreach (u; us) {switch (deg[u]) {case +1: {ok = ok && (s == -1);s = u;} break;case 0: {//} break;case -1: {ok = ok && (t == -1);t = u;} break;default: {ok = false;}}}foreach (u; us) {ok = ok && (uf.root(us[0]) == uf.root(u));}if (!ok) {writeln(0);continue;}debug {writeln("adj = ", adj);writeln("us = ", us);writeln("s = ", s, ", t = ", t);}const usLen = cast(int)(us.length);auto outdeg = new int[usLen];foreach (i; 0 .. usLen) foreach (j; 0 .. usLen) {if (adj[us[i]][us[j]]) {++outdeg[i];}}int[] as, bs, cs;foreach (k; 0 .. M) {if (used[A[k]] && used[B[k]]) {as ~= us.lowerBound(A[k]);bs ~= us.lowerBound(B[k]);cs ~= +1;}}if (s != -1) {// add (t, s)s = us.lowerBound(s);t = us.lowerBound(t);++outdeg[t];as ~= t;bs ~= s;cs ~= -1;}const n = usLen - 1;const m = cast(int)(as.length);debug {writeln("outdeg = ", outdeg);writeln("as = ", as);writeln("bs = ", bs);writeln("cs = ", cs);}debug {// O(N^3)auto a = new Mint[][](n, n);foreach (i; 0 .. n) foreach (j; 0 .. n) {if (adj[us[i]][us[j]]) {a[i][j] -= 1;}}if (s != -1) {if (s < n && t < n) {a[t][s] -= 1;}}foreach (i; 0 .. n) {a[i][i] += outdeg[i];}Mint brt = 1;foreach (h; 0 .. n) {foreach (i; h .. n) {if (a[i][h]) {if (h != i) {brt *= -1;}swap(a[h], a[i]);break;}}brt *= a[h][h];if (!a[h][h]) {break;}const ahhInv = a[h][h].inv;foreach (i; h + 1 .. n) {const coef = a[i][h] * ahhInv;foreach (j; h .. n) {a[i][j] -= coef * a[h][j];}}}writeln("brt det = ", brt);foreach (i; 0 .. usLen) {foreach (d; 1 .. outdeg[i]) {brt *= d;}}if (s == -1) {brt *= (N^^2 - M);}writeln("brt = ", brt);}Mint ans;for (; ; ) {auto dots = new Mint[2 * n];auto coef = new Mint[n];foreach (i; 0 .. n) {coef[i] = xrand();}auto diag = new Mint[n];foreach (i; 0 .. n) {diag[i] = 1 + xrand() % (MO - 1);}auto vec = new Mint[n];foreach (i; 0 .. n) {vec[i] = xrand();}foreach (h; 0 .. 2 * n) {// dotforeach (i; 0 .. n) {dots[h] += coef[i] * vec[i];}// mul diagvec[] *= diag[];// mul Laplacianauto vecNext = new Mint[n];vecNext[] = -vec.sum;foreach (i; 0 .. n) {vecNext[i] += outdeg[i] * vec[i];}foreach (k; 0 .. m) {if (as[k] < n && bs[k] < n) {vecNext[as[k]] += cs[k] * vec[bs[k]];}}vec = vecNext;}const res = findLinearRecurrence(dots);if (res.length == n + 1) {ans = (-1)^^(n & 1) * res[n];foreach (i; 0 .. n) {ans /= diag[i];}debug {writeln("det = ", ans);}break;}}foreach (i; 0 .. usLen) {foreach (d; 1 .. outdeg[i]) {ans *= d;}}if (s == -1) {ans *= (N^^2 - M);}writeln(ans);}} catch (EOFException e) {}}