結果

問題 No.214 素数サイコロと合成数サイコロ (3-Medium)
コンテスト
ユーザー te-sh
提出日時 2017-08-10 17:26:58
言語 D
(dmd 2.109.1)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,851 bytes
コンパイル時間 413 ms
コンパイル使用メモリ 130,148 KB
最終ジャッジ日時 2024-11-14 20:11:40
合計ジャッジ時間 802 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、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, true))` 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, true), char)` error instantiating
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/format/write.d(632):        instantiated from here: `formatValue!(LockingTextWriter, FactorRing!(1000000007, true), char)`
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/stdio.d(1759):        instantiated from here: `formattedWrite!(LockingTextWriter, char, FactorRing!(1000000007, true))`
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/stdio.d(4277):        instantiated from here: `write!(FactorRing!(1000000007, true), char)`
Main.d(33):        instantiated from here: `writeln!(FactorRing!(1000000007, true))`

ソースコード

diff # 

import std.algorithm, std.conv, std.range, std.stdio, std.string;

const mod = 10 ^^ 9 + 7;
alias FactorRing!(mod, true) mint;

const dpi = [2,3,5,7,11,13];
const dci = [4,6,8,9,10,12];

void main()
{
  auto rd = readln.split, n = rd[0].to!long, p = rd[1].to!int, c = rd[2].to!int;
  auto m = (dpi.maxElement * p + dci.maxElement * c).to!long;
  auto cpi = calcCombi!mint(dpi, p);
  auto cci = calcCombi!mint(dci, c);

  auto ci = new mint[](m+1);
  if (p == 0) {
    ci = cci;
  } else if (c == 0) {
    ci = cpi;
  } else {
    foreach (i, cp; cpi)
      foreach (j, cc; cci)
        ci[i+j] += cp * cc;
  }

  if (n <= m) {
    auto ai = new mint[](n+1);
    foreach (i; 1..n+1)
      foreach (j; 1..m+1)
        ai[i] += (i-j > 0 ? ai[i-j] : mint(1)) * ci[j];

    writeln(ai[n]);
  } else {
    auto ai = new mint[](m+1);
    foreach (i; 1..m+1)
      foreach (j; 1..m+1)
        ai[i] += (i-j > 0 ? ai[i-j] : mint(1)) * ci[j];

    auto di = ci.dup; di.reverse();

    auto r = kitamasa(di[0..$-1], ai[1..$], n-1);
    writeln(r);
  }
}

T[] calcCombi(T)(const int[] di, int c)
{
  if (c == 0) return [];

  auto n = di.length.to!int, md = di.maxElement * c;
  auto dp = new T[][](c+1, md+1), dp2 = new T[][](c+1, md+1);
  dp[0][0] = T(1);

  foreach (d; di) {
    foreach (j; 0..c+1) {
      dp2[j][] = dp[j][];
      foreach (k; 1..j+1)
        foreach (i; k*d..md+1)
          dp[j][i] += dp2[j-k][i-k*d];
    }
  }

  return dp[c];
}

T kitamasa(T, U)(T[] a, T[] x, U k)
{
  import std.range;

  auto n = a.length;
  auto t = new T[](n*2+1);

  T[] rec(U k)
  {
    auto c = new T[](n);
    if (k < n) {
      c[k] = 1;
    } else {
      auto b = rec(k/2);
      t[] = T(0);
      foreach (i; 0..n)
        foreach (j; 0..n)
          t[i+j+(k&1)] += b[i] * b[j];
      foreach_reverse (i; n..n*2)
        foreach (j; 0..n)
          t[i-n+j] += a[j] * t[i];
      c[] = t[0..n][];
    }
    return c;
  }

  auto c = rec(k);

  auto r = T(0);
  foreach (i; 0..n) r += c[i] * x[i];

  return r;
}

struct FactorRing(int m, bool pos = false)
{
  version(BigEndian) {
    union { long vl; struct { int vi2; int vi; } }
  } else {
    union { long vl; int vi; }
  }

  @property int toInt() { return vi; }
  alias toInt this;

  this(bool runMod = false)(int v)
  {
    static if (runMod) vi = mod(v);
    else vi = v;
  }

  ref FactorRing!(m, pos) 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 (m < int.max / 2) {
    pure auto opBinary(string op: "+")(int rhs) const { return FactorRing!(m, pos)(mod(vi + rhs)); }
    pure auto opBinary(string op: "-")(int rhs) const { return FactorRing!(m, pos)(mod(vi - rhs)); }
  } else {
    pure auto opBinary(string op: "+")(int rhs) const { return FactorRing!(m, pos)(mod(vl + rhs)); }
    pure auto opBinary(string op: "-")(int rhs) const { return FactorRing!(m, pos)(mod(vl - rhs)); }
  }
  pure auto opBinary(string op: "*")(int rhs) const { return FactorRing!(m, pos)(mod(vl * rhs)); }

  pure auto opBinary(string op)(FactorRing!(m, pos) rhs) const
    if (op == "+" || op == "-" || op == "*") { return opBinary!op(rhs.vi); }

  static if (m < int.max / 2) {
    auto opOpAssign(string op: "+")(int rhs) { vi = mod(vi + rhs); }
    auto opOpAssign(string op: "-")(int rhs) { vi = mod(vi - rhs); }
  } else {
    auto opOpAssign(string op: "+")(int rhs) { vi = mod(vl + rhs); }
    auto opOpAssign(string op: "-")(int rhs) { vi = mod(vl - rhs); }
  }
  auto opOpAssign(string op: "*")(int rhs) { vi = mod(vl * rhs); }

  auto opOpAssign(string op)(FactorRing!(m, pos) rhs)
    if (op == "+" || op == "-" || op == "*") { return opOpAssign!op(rhs.vi); }
}
0