結果
| 問題 | No.650 行列木クエリ |
| ユーザー |
 te-sh
|
| 提出日時 | 2018-04-19 13:26:15 |
| 言語 | D (dmd 2.106.1) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 8,319 bytes |
| コンパイル時間 | 497 ms |
| コンパイル使用メモリ | 148,588 KB |
| 最終ジャッジ日時 | 2024-11-14 20:24:47 |
| 合計ジャッジ時間 | 1,628 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/format/internal/write.d(143): Error: cannot implicitly convert expression `obj` of type `const(FactorRing!(1000000007, false))` to `int` /home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/format/write.d(1239): Error: template instance `std.format.internal.write.formatValueImpl!(LockingTextWriter, FactorRing!(1000000007, false), char)` error instantiating /home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/format/write.d(632): instantiated from here: `formatValue!(LockingTextWriter, FactorRing!(1000000007, false), char)` /home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/stdio.d(1759): instantiated from here: `formattedWrite!(LockingTextWriter, char, FactorRing!(1000000007, false))` /home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/stdio.d(4277): instantiated from here: `write!(FactorRing!(1000000007, false), string, FactorRing!(1000000007, false), string, FactorRing!(1000000007, false), string, FactorRing!(1000000007, false), char)` Main.d(47): instantiated from here: `writeln!(FactorRing!(1000000007, false), string, FactorRing!(1000000007, false), string, FactorRing!(1000000007, false), string, FactorRing!(1000000007, false))`
ソースコード
import std.algorithm, std.container, std.conv, std.math, std.range, std.typecons, std.stdio, std.string;
auto rdsp(){return readln.splitter;}
void pick(R,T)(ref R r,ref T t){t=r.front.to!T;r.popFront;}
void pickV(R,T...)(ref R r,ref T t){foreach(ref v;t)pick(r,v);}
void readV(T...)(ref T t){auto r=rdsp;foreach(ref v;t)pick(r,v);}
void readC(T...)(size_t n,ref T t){foreach(ref v;t)v=new typeof(v)(n);foreach(i;0..n){auto r=rdsp;foreach(ref v;t)pick(r,v[i]);}}
const mod = 10^^9+7;
alias mint = FactorRing!mod;
alias mat = Matrix!mint;
alias segTree = SegmentTree!(mat, "a*b");
void main()
{
int n; readV(n);
int[] a, b; readC(n-1, a, b);
auto g = Graph!()(n);
foreach (ai, bi; lockstep(a, b)) g.addEdgeB(ai, bi);
auto t = g.makeTree.rootify(0).hlDecomposition;
t.makePath(0);
auto st = new segTree[](t.paths.length);
foreach (i, ref sti; st)
sti = new segTree(t.paths[i].length, mat.unit(2));
int q; readV(q);
foreach (_; 0..q) {
auto rd = rdsp;
string typ; pick(rd, typ);
switch (typ) {
case "x":
int v, c1, c2, c3, c4; pickV(rd, v, c1, c2, c3, c4);
auto e = t.parent[a[v]] == b[v] ? a[v] : b[v];
st[t.path[e]][t.depthInPath(e)] = mat([[mint(c1), mint(c2)], [mint(c3), mint(c4)]]);
break;
case "g":
int i, j; pickV(rd, i, j);
auto ans = mat.unit(2);
while (t.head[i] != t.head[j]) {
ans = st[t.path[j]][0..t.depthInPath(j)+1] * ans;
j = t.parent[t.head[j]];
}
ans = st[t.path[i]][t.depthInPath(i)+1..t.depthInPath(j)+1] * ans;
writeln(ans[0][0], " ", ans[0][1], " ", ans[1][0], " ", ans[1][1]);
break;
default:
assert(0);
}
}
}
struct Graph(N = int)
{
alias Node = N;
Node n;
Node[][] g;
alias g this;
this(Node n) { this.n = n; g = new Node[][](n); }
void addEdge(Node u, Node v) { g[u] ~= v; }
void addEdgeB(Node u, Node v) { g[u] ~= v; g[v] ~= u; }
}
struct Tree(Graph)
{
import std.algorithm, std.container;
alias Node = Graph.Node;
Graph g;
alias g this;
Node root;
Node[] parent;
int[] size, depth;
this(ref Graph g) { this.g = g; this.n = g.n; }
ref auto rootify(Node r)
{
this.root = r;
parent = new Node[](g.n);
depth = new int[](g.n);
depth[] = -1;
struct UP { Node u, p; }
auto st1 = SList!UP(UP(r, r));
auto st2 = SList!UP();
while (!st1.empty) {
auto up = st1.front, u = up.u, p = up.p; st1.removeFront();
parent[u] = p;
depth[u] = depth[p] + 1;
foreach (v; g[u])
if (v != p) {
st1.insertFront(UP(v, u));
st2.insertFront(UP(v, u));
}
}
size = new int[](g.n);
size[] = 1;
while (!st2.empty) {
auto up = st2.front, u = up.u, p = up.p; st2.removeFront();
size[p] += size[u];
}
return this;
}
auto children(Node u) { return g[u].filter!(v => v != parent[u]); }
}
ref auto makeTree(Graph)(ref Graph g) { return Tree!Graph(g); }
struct HlDecomposition(Tree)
{
import std.container;
alias Node = Tree.Node;
Tree t;
alias t this;
Node[] head, path;
Node[][] paths;
this(ref Tree t)
{
this.t = t;
auto n = t.n;
head = new Node[](n); head[] = n;
struct US { Node u, s; }
auto st = SList!US(US(t.root, t.root));
while (!st.empty) {
auto us = st.front, u = us.u, s = us.s; st.removeFront();
head[u] = s;
auto z = n;
foreach (v; t[u])
if (head[v] == n && (z == n || t.size[z] < t.size[v])) z = v;
foreach (v; t[u])
if (head[v] == n) st.insertFront(US(v, v == z ? s : v));
}
}
auto makePath(Node r)
{
auto pathIndex = 0;
path = new Node[](t.n);
auto q = DList!Node(r);
while (!q.empty) {
auto u = q.front; q.removeFront();
if (u == head[u]) {
path[u] = pathIndex++;
paths ~= [u];
} else {
path[u] = path[head[u]];
paths[path[u]] ~= u;
}
foreach (v; t[u])
if (v != t.parent[u]) q.insertBack(v);
}
}
auto depthInPath(Node n)
{
return t.depth[n] - t.depth[head[n]];
}
auto lca(Node u, Node v)
{
while (head[u] != head[v])
if (t.depth[head[u]] < t.depth[head[v]]) v = t.parent[head[v]];
else u = t.parent[head[u]];
return t.depth[u] < t.depth[v] ? u : v;
}
}
ref auto hlDecomposition(Tree)(ref Tree t) { return HlDecomposition!(Tree)(t); }
class SegmentTree(T, alias pred = "a + b")
{
import core.bitop, std.functional;
alias predFun = binaryFun!pred;
const size_t n, an;
T[] buf;
T unit;
this(size_t n, T unit = T.init)
{
this.n = n;
this.unit = unit;
an = n == 1 ? 1 : (1 << ((n-1).bsr + 1));
buf = new T[](an*2);
if (T.init != unit) buf[] = unit;
}
this(T[] init, T unit = T.init)
{
this(init.length, unit);
buf[an..an+n][] = init[];
foreach_reverse (i; 1..an)
buf[i] = predFun(buf[i*2], buf[i*2+1]);
}
void opIndexAssign(T val, size_t i)
{
buf[i += an] = val;
while (i /= 2)
buf[i] = predFun(buf[i*2], buf[i*2+1]);
}
pure T opSlice(size_t l, size_t r)
{
l += an; r += an;
T r1 = unit, r2 = unit;
while (l != r) {
if (l % 2) r1 = predFun(r1, buf[l++]);
if (r % 2) r2 = predFun(buf[--r], r2);
l /= 2; r /= 2;
}
return predFun(r1, r2);
}
pure T opIndex(size_t i) { return buf[i+an]; }
pure size_t opDollar() { return n; }
}
struct Matrix(T)
{
size_t r, c;
T[][] a;
alias a this;
static ref auto unit(size_t n)
{
auto r = Matrix!T(n, n);
foreach (i; 0..n) r[i][i] = 1;
return r;
}
this(size_t r, size_t c)
{
this.r = r; this.c = c;
a = new T[][](r, c);
static if (T.init != 0) foreach (i; 0..r) a[i][] = 0;
}
this(T[][] b)
{
r = b.length;
c = b[0].length;
a = b;
}
ref auto dup() { auto x = Matrix!T(r, c); foreach (i; 0..r) x[i][] = a[i][]; return x; }
ref auto opBinary(string op)(Matrix!T b) if (op == "+" || op == "-") in { assert(r == b.r && c == b.c); } body
{
auto x = Matrix!T(r, c);
foreach (i; 0..r) foreach (j; 0..c) x[i][j] = mixin("a[i][j]"~op~"b[i][j]");
return x;
}
ref auto opBinary(string op: "*")(Matrix!T b) in { assert(c == b.r); } body
{
auto x = Matrix!T(r, b.c);
foreach (i; 0..r) foreach (j; 0..b.c) foreach (k; 0..c) x[i][j] += a[i][k]*b[k][j];
return x;
}
ref auto opBinary(string op: "*")(T[] b) in { assert(c == b.length); } body
{
auto x = new T[](r);
static if (T.init != 0) x[] = 0;
foreach (i; 0..r) foreach (j; 0..c) x[i] += a[i][j]*b[j];
return x;
}
}
struct FactorRing(int m, bool pos = false)
{
version(BigEndian) union { long vl; struct { int vi2; int vi; } } else union { long vl; int vi; }
alias FR = FactorRing!(m, pos);
@property static init() { return FR(0); }
@property int value() { return vi; }
@property void value(int v) { vi = mod(v); }
alias value this;
this(int v) { vi = v; }
this(int v, bool runMod) { vi = runMod ? mod(v) : v; }
this(long v) { vi = mod(v); }
ref auto opAssign(int v) { vi = v; return this; }
pure auto mod(int v) const { static if (pos) return v%m; else return (v%m+m)%m; }
pure auto mod(long v) const { static if (pos) return cast(int)(v%m); else return cast(int)((v%m+m)%m); }
static if (!pos) pure ref auto opUnary(string op: "-")() { return FR(mod(-vi)); }
static if (m < int.max / 2) {
pure ref auto opBinary(string op)(int r) if (op == "+" || op == "-") { return FR(mod(mixin("vi"~op~"r"))); }
ref auto opOpAssign(string op)(int r) if (op == "+" || op == "-") { vi = mod(mixin("vi"~op~"r")); return this; }
} else {
pure ref auto opBinary(string op)(int r) if (op == "+" || op == "-") { return FR(mod(mixin("vl"~op~"r"))); }
ref auto opOpAssign(string op)(int r) if (op == "+" || op == "-") { vi = mod(mixin("vl"~op~"r")); return this; }
}
pure ref auto opBinary(string op: "*")(int r) { return FR(mod(vl*r)); }
ref auto opOpAssign(string op: "*")(int r) { vi = mod(vl*r); return this; }
pure ref auto opBinary(string op)(ref FR r) if (op == "+" || op == "-" || op == "*") { return opBinary!op(r.vi); }
ref auto opOpAssign(string op)(ref FR r) if (op == "+" || op == "-" || op == "*") { return opOpAssign!op(r.vi); }
}