結果

問題 No.213 素数サイコロと合成数サイコロ (3-Easy)
コンテスト
ユーザー te-sh
提出日時 2017-05-16 16:26:36
言語 D
(dmd 2.109.1)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,630 bytes
コンパイル時間 678 ms
コンパイル使用メモリ 137,236 KB
最終ジャッジ日時 2024-11-14 20:00:47
合計ジャッジ時間 1,037 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、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(34):        instantiated from here: `writeln!(FactorRing!1000000007)`

ソースコード

diff # 

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

const p = 10 ^^ 9 + 7;
alias FactorRing!p 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(dpi, p);
  auto cci = calcCombi(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+m);
    ai[0] = 1;
    foreach (i; 1..n+m)
      foreach (j; 1..m+1)
        if (i-j >= 0 && i-j < n)
          ai[i] += ai[i-j] * ci[j];
    writeln(ai[n..$].sum);
  } else {
    auto ai = new mint[](m+1);
    ai[0] = 1;
    foreach (i; 1..m+1)
      foreach (j; 1..m+1)
        if (i-j >= 0)
          ai[i] += ai[i-j] * ci[j];

    auto mc = new mint[][](m, m);
    mc[0][] = ci[1..$][];
    foreach (i; 0..m-1) mc[i+1][i] = mint(1);

    auto mi = new mint[][](m, m);
    foreach (i; 0..m) mi[i][i] = mint(1);

    auto mq = repeatedSquare!(mint[][], matMul)(mc, n-m, mi);

    auto bi = ai.dup; bi.reverse();
    ai = matMulVec(mq, bi[0..$-1]);
    ai.reverse();

    auto ri = new mint[](m*2);
    ri[1..m+1][] = ai[];
    foreach (i; 1..m)
      foreach (j; 1..m+1)
        if (m+i-j > 0 && m+i-j < m)
          ri[m+i] += ri[m+i-j] * ci[j];

    writeln(ri[m..$].sum);
  }
}

mint[] calcCombi(const int[] di, int c)
{
  auto n = di.length.to!int;
  if (c == 0)
    return [];

  auto ri = new int[][][](c);
  ri[0] = n.iota.map!(i => [i.to!int]).array;
  foreach (i; 1..c)
    ri[i] = ri[i-1].map!(r => iota(r.back, n).map!(d => r ~ d)).joiner.array;

  auto ci = new mint[](di.maxElement * c + 1);
  foreach (r; ri[$-1])
    ci[di.indexed(r).sum] += 1;

  return ci;
}

T repeatedSquare(T, alias pred = "a * b", U)(T a, U n, T init)
{
  import std.functional;
  alias predFun = binaryFun!pred;

  if (n == 0) return init;

  auto r = init;
  while (n > 0) {
    if ((n & 1) == 1)
      r = predFun(r, a);
    a = predFun(a, a);
    n >>= 1;
  }

  return r;
}

T[][] matMul(T)(T[][] a, T[][] b)
{
  auto l = b.length, m = a.length, n = b[0].length;
  auto c = new T[][](m, n);
  foreach (i; 0..m)
    foreach (j; 0..n)
      foreach (k; 0..l)
        c[i][j] += a[i][k] * b[k][j];
  return c;
}

T[] matMulVec(T)(T[][] a, T[] b)
{
  auto l = b.length, m = a.length;
  auto c = new T[](m);
  foreach (i; 0..m)
    foreach (j; 0..l)
      c[i] += a[i][j] * b[j];
  return c;
}

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

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

  pure auto opBinary(string op: "+")(int rhs) const { return FactorRing!m(v + rhs); }
  pure auto opBinary(string op: "-")(int rhs) const { return FactorRing!m(v - rhs); }
  pure auto opBinary(string op: "*")(int rhs) const { return FactorRing!m(v * rhs); }

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

  auto opOpAssign(string op: "+")(int rhs) { v = mod(v + rhs); }
  auto opOpAssign(string op: "-")(int rhs) { v = mod(v - rhs); }
  auto opOpAssign(string op: "*")(int rhs) { v = mod(v * rhs); }

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