#252447 (D) No.650 行列木クエリ

• 問題: No.650 行列木クエリ
• ユーザー: te-sh
• 提出日時: 2018-04-19 13:26:15
• 言語: D (dmd 2.109.1)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 8,319 bytes
• コンパイル時間: 497 ms
• コンパイル使用メモリ: 148,588 KB
• 最終ジャッジ日時: 2024-11-14 20:24:47
• 合計ジャッジ時間: 1,628 ms
• ジャッジサーバーID （参考情報）: judge1 / judge5

コンパイルメッセージ

/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); }
}