結果

問題 No.147 試験監督（2）
コンテスト
ユーザー te-sh
提出日時 2017-02-02 11:46:46
言語 D
(dmd 2.109.1)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,101 bytes
コンパイル時間 400 ms
コンパイル使用メモリ 134,456 KB
最終ジャッジ日時 2024-11-14 19:56:12
合計ジャッジ時間 910 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、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)` 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, char)` error instantiating
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/format/write.d(632):        instantiated from here: `formatValue!(LockingTextWriter, FactorRing!1000000007, char)`
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/stdio.d(1759):        instantiated from here: `formattedWrite!(LockingTextWriter, char, FactorRing!1000000007)`
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/stdio.d(4277):        instantiated from here: `write!(FactorRing!1000000007, char)`
Main.d(19):        instantiated from here: `writeln!(FactorRing!1000000007)`

ソースコード

diff # 

import std.algorithm, std.conv, std.range, std.stdio, std.string;
import std.bigint;    // BigInt

const auto p = 10^^9 + 7;
alias FactorRing!p mint;

void main()
{
  auto n = readln.chomp.to!size_t;

  auto r = mint(1);
  foreach (_; n.iota) {
    auto rd = readln.split, c = rd[0].to!long, d = rd[1].to!BigInt;
    auto e = fibonacchi!(mint, long)(c + 2);
    auto f = (d % (p - 1)).to!int;
    r = r * (e.toInt == 0 ? mint(0) : e ^^ f);
  }

  writeln(r);
}

auto fibonacchi(T, U)(U n)
{
  static T[4][U.sizeof * 8] buf;
  buf[0] = [T(1), T(1), T(1), T(0)];
  static sf = 0;

  T[4] matProd(T)(T[4] a, T[4] b) {
    return [a[0] * b[0] + a[1] * b[2],
            a[0] * b[1] + a[1] * b[3],
            a[2] * b[0] + a[3] * b[2],
            a[2] * b[1] + a[3] * b[3]];
  }

  auto b = 0;
  T[4] r = [T(1), T(0), T(0), T(1)];
  for (; n > 0; ++b, n >>= 1) {
    if ((n & U(1)) != 0) {
      while (b > sf) {
        buf[sf + 1] = matProd(buf[sf], buf[sf]);
        ++sf;
      }
      r = matProd(r, buf[b]);
    }
  }

  return r[1];
}

struct FactorRing(int m) {
  long v;

  @property int toInt() { return v.to!int; }
  alias toInt this;

  this(T)(T _v) { v = mod(_v); }

  ref FactorRing!m opAssign(int _v) {
    v = mod(_v);
    return this;
  }

  auto mod(long _v) { return _v > 0 ? _v % m : ((_v % m) + m) % m; }

  auto opBinary(string op: "+")(FactorRing!m rhs) { return FactorRing!m(v + rhs.v); }
  auto opBinary(string op: "-")(FactorRing!m rhs) { return FactorRing!m(v - rhs.v); }
  auto opBinary(string op: "*")(FactorRing!m rhs) { return FactorRing!m(v * rhs.v); }
  auto opBinary(string op: "^^")(FactorRing!m rhs) { return pow(this, rhs.toInt); }

  auto opBinary(string op)(int rhs)
    if (op == "+" || op == "-" || op == "*") { return opBinary!op(FactorRing!m(rhs)); }
  auto opBinary(string op: "^^")(int rhs) { return pow(this, rhs); }

  auto pow(FactorRing!m a, int b) {
    if (b == 0) return FactorRing!m(1);
    if (a == 0) return FactorRing!m(0);
    auto c = FactorRing!m(1);
    for (; b > 0; a = a * a, b >>= 1)
      if ((b & 1) == 1) c = c * a;
    return c;
  }
}
0