#180288 (D) No.303 割れません

提出ソース

結果

問題	No.303 割れません
ユーザー	te-sh
提出日時	2017-06-15 11:23:16
言語	D (dmd 2.106.1)
結果	RE
実行時間	-
コード長	6,088 bytes
コンパイル時間	1,463 ms
コンパイル使用メモリ	140,940 KB
実行使用メモリ	15,420 KB
最終ジャッジ日時	2023-09-03 14:22:41
合計ジャッジ時間	15,809 ms
ジャッジサーバーID （参考情報）	judge13 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,376 KB
testcase_01	AC	1 ms 4,380 KB
testcase_02	AC	1 ms 4,380 KB
testcase_03	RE	-
testcase_04	RE	-
testcase_05	RE	-
testcase_06	RE	-
testcase_07	RE	-
testcase_08	RE	-
testcase_09	RE	-
testcase_10	AC	1 ms 4,380 KB
testcase_11	RE	-
testcase_12	RE	-
testcase_13	RE	-
testcase_14	RE	-
testcase_15	RE	-
testcase_16	AC	1 ms 4,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

alias BigInt2!9 Bi;

void main()
{
  auto l = readln.chomp.to!int;

  if (l == 1) {
    writeln(1);
    writeln(1);
  } else if (l == 2) {
    writeln(3);
    writeln("INF");
  } else {
    writeln(l);
    auto r = calc(l);
    if (l % 2 == 0) {
      auto s = calc(l/2);
      writeln((r - s * s).toString);
    } else {
      writeln(r.toString);
    }
  }
}

auto calc(int l)
{
  auto o = Bi(1), z = Bi(0);
  auto a = [[o,o],[o,z]];
  auto im = [[o,z],[z,o]];

  auto b = repeatedSquare!(Bi[][], matMul)(a, l-2, im);
  return b[0][0] + b[0][1];
}

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

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;

  static buf = new T[](32);
  static bufFilled = 0;

  if (bufFilled == 0)
    buf[bufFilled++] = a;

  auto r = init, i = 0;
  while (n > 0) {
    if ((n & 1) == 1)
      r = predFun(r, buf[i]);
    if (++i == bufFilled)
      buf[bufFilled++] = predFun(buf[i-1], buf[i-1]);
    n >>= 1;
  }

  return r;
}

struct BigInt2(long w = 9)
{
  import std.algorithm, std.array, std.conv, std.range, std.string;

  const base = 10 ^^ w;
  int[] z;
  int sign = 1;

  this(long v)
  {
    if (v < 0) { sign = -1; v = -v; }
    for (; v > 0; v /= base) z ~= (v % base).to!int;
  }

  this(int[] z, int sign)
  {
    this.z = z;
    this.sign = sign;
  }

  pure auto dup() const
  {
    return BigInt2!w(z.dup, sign);
  }

  pure auto opCmp(const BigInt2!w v) const
  {
    if (sign != v.sign)
      return sign < v.sign ? -1 : 1;
    if (z.length != v.z.length)
      return z.length * sign < v.z.length * v.sign ? -1 : 1;
    foreach_reverse (i; 0..z.length)
      if (z[i] != v.z[i])
        return z[i] < v.z[i] ? -sign : sign;
    return 0;
  }

  pure auto toString()
  {
    auto ap = appender!string();

    if (z.empty) {
      ap.put("0");
      return ap.data;
    }

    if (sign == -1) ap.put("-");
    ap.put(format("%d", z[$-1]));
    auto fmt = "%0" ~ w.to!string ~ "d";
    foreach_reverse (zi; z[0..$-1]) ap.put(format(fmt, zi));
    return ap.data;
  }

  pure auto opUnary(string op: "-")() const
  {
    auto res = dup;
    if (!z.empty) res.sign = -sign;
    return res;
  }

  pure auto opBinary(string op: "+")(const BigInt2!w v) const
  {
    if (v.z.empty) return dup;
    if (sign == v.sign) {
      auto res = v.dup;
      for (int i = 0, carry = 0; i < max(z.length, v.z.length) || carry; ++i) {
        if (i == res.z.length)
          res.z ~= 0;
        res.z[i] += carry + (i < z.length ? z[i] : 0);
        carry = res.z[i] >= base;
        if (carry) res.z[i] -= base;
      }
      return res;
    }
    return this - (-v);
  }

  pure auto opBinary(string op: "-")(const BigInt2!w v) const
  {
    if (v.z.empty) return dup;
    if (sign == v.sign) {
      if (sign == 1 && this >= v || sign == -1 && this <= v) {
        auto res = dup;
        for (int i = 0, carry = 0; i < v.z.length || carry; ++i) {
          res.z[i] -= carry + (i < v.z.length ? v.z[i] : 0);
          carry = res.z[i] < 0;
          if (carry) res.z[i] += base;
        }
        res.trim();
        return res;
      }
      return -(v - this);
    }
    return this + (-v);
  }

  pure auto opBinary(string op: "*")(const BigInt2!w v) const
  {
    if (z.empty || v.z.empty) return BigInt2!w(0);
    auto a6 = convertBase(z, w, 6);
    auto b6 = convertBase(v.z, w, 6);
    auto a = a6.to!(long[]), b = b6.to!(long[]);
    while (a.length < b.length) a ~= 0L;
    while (b.length < a.length) b ~= 0L;
    while (a.length & (a.length - 1)) { a ~= 0L; b ~= 0L; }
    auto c = karatsuba(a, b);
    BigInt2!w res;
    res.sign = sign * v.sign;
    for (int i = 0, carry = 0; i < c.length; ++i) {
      auto cur = c[i] + carry;
      res.z ~= (cur % 1000000).to!int;
      carry = (cur / 1000000).to!int;
    }
    res.z = convertBase(res.z, 6, w);
    res.trim();
    return res;
  }

  pure int[] convertBase(const int[] a, int oldDigits, int newDigits) const
  {
    auto p = new long[](max(oldDigits, newDigits) + 1);
    p[0] = 1;
    foreach (i; 1..p.length) p[i] = p[i-1] * 10;
    int[] res;
    long cur = 0;
    int curDigits = 0;
    foreach (i; 0..a.length) {
      cur += a[i] * p[curDigits];
      curDigits += oldDigits;
      while (curDigits >= newDigits) {
        res ~= (cur % p[newDigits]).to!int;
        cur /= p[newDigits];
        curDigits -= newDigits;
      }
    }
    res ~= cur.to!int;
    while (!res.empty && res[$-1] == 0) res = res[0..$-1];
    return res;
  }

  pure long[] karatsuba(const long[] a, const long[] b) const
  {
    auto n = a.length;
    auto res = new long[](n * 2);
    if (n <= 32) {
      foreach (i; 0..n)
        foreach (j; 0..n)
          res[i+j] += a[i] * b[j];
      return res;
    }

    auto k = n >> 1;
    auto a1 = a[0..k].dup, a2 = a[k..$].dup;
    auto b1 = b[0..k].dup, b2 = b[k..$].dup;

    auto a1b1 = karatsuba(a1, b1);
    auto a2b2 = karatsuba(a2, b2);

    foreach (i; 0..k) a2[i] += a1[i];
    foreach (i; 0..k) b2[i] += b1[i];

    auto r = karatsuba(a2, b2);
    foreach (i; 0..a1b1.length) r[i] -= a1b1[i];
    foreach (i; 0..a2b2.length) r[i] -= a2b2[i];

    foreach (i; 0..r.length) res[i+k] += r[i];
    foreach (i; 0..a1b1.length) res[i] += a1b1[i];
    foreach (i; 0..a2b2.length) res[i+n] += a2b2[i];

    return res;
  }

  auto opOpAssign(string op)(const BigInt2!w v)
    if (op == "+" || op == "-" || op == "*")
  {
    auto res = opBinary!op(v);
    z = res.z;
    sign = res.sign;
    return this;
  }

  auto trim()
  {
    while (!z.empty && z[$-1] == 0) z = z[0..$-1];
    if (z.empty) sign = 1;
  }
}

yukicoder

結果

テストケース

ソースコード