#312414 (D) No.695 square1001 and Permutation 4

• 問題: No.695 square1001 and Permutation 4
• ユーザー: 👑 hos.lyric
• 提出日時: 2019-01-24 10:57:41
• 言語: D (dmd 2.106.1)
• 結果: AC
• 実行時間: 2,121 ms / 7,000 ms
• コード長: 4,410 bytes
• コンパイル時間: 857 ms
• コンパイル使用メモリ: 121,728 KB
• 実行使用メモリ: 41,540 KB
• 最終ジャッジ日時: 2024-06-13 03:36:25
• 合計ジャッジ時間: 12,457 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	106 ms; 5,376 KB
testcase_02	AC	55 ms; 12,160 KB
testcase_03	AC	54 ms; 12,160 KB
testcase_04	AC	528 ms; 12,160 KB
testcase_05	AC	482 ms; 12,160 KB
testcase_06	AC	860 ms; 21,888 KB
testcase_07	AC	1,062 ms; 21,888 KB
testcase_08	AC	844 ms; 21,888 KB
testcase_09	AC	906 ms; 21,888 KB
testcase_10	AC	193 ms; 6,272 KB
testcase_11	AC	2,037 ms; 41,472 KB
testcase_12	AC	1,532 ms; 41,472 KB
testcase_13	AC	2,121 ms; 41,540 KB

ソースコード

import std.conv, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.container, std.math, std.numeric, std.range, std.regex, std.typecons;
import core.bitop;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }

bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }

int binarySearch(T)(in T[] as, in bool delegate(T) test) { int low = -1, upp = cast(int)(as.length); for (; low + 1 < upp; ) { int mid = (low + upp) >> 1; (test(as[mid]) ? low : upp) = mid; } return upp; }
int lowerBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a < val)); }
int upperBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a <= val)); }


// a^-1 (mod m)
long modInv(long a, long m)
in {
  assert(m > 0, "modInv: m > 0 must hold");
}
do {
  long b = m, x = 1, y = 0, t;
  for (; ; ) {
    t = a / b;
    a -= t * b;
    if (a == 0) {
      assert(b == 1 || b == -1, "modInv: gcd(a, m) != 1");
      if (b == -1) {
        y = -y;
      }
      return (y < 0) ? (y + m) : y;
    }
    x -= t * y;
    t = b / a;
    b -= t * a;
    if (b == 0) {
      assert(a == 1 || a == -1, "modInv: gcd(a, m) != 1");
      if (a == -1) {
        x = -x;
      }
      return (x < 0) ? (x + m) : x;
    }
    y -= t * x;
  }
}

// Find the smallest x (>= 0) s.t. x == a[i] (mod m[i]), mod m0
//   x = y[0] + m[0] y[1] + m[0] m[1] y[2] + ... + m[0] ... m[n - 1] y[n - 1]
//   m[i]'s must be coprime
long garner(long[] a, long[] m, long m0)
in {
  foreach (i; 0 .. m.length) {
    assert(0 < m[i] && m[i] <= 0x7fffffff, "garner: 0 < m < 2^31 must hold");
  }
}
do {
  long t;
  auto y = new long[m.length];
  foreach (i; 0 .. m.length) {
    y[i] = a[i] % m[i];
    t = 1;
    foreach (j; 0 .. i) {
      (y[i] -= t * y[j]) %= m[i];
      (t *= m[j]) %= m[i];
    }
    if (((y[i] *= modInv(t, m[i])) %= m[i]) < 0) {
      y[i] += m[i];
    }
  }
  long x = 0;
  t = 1;
  foreach (i; 0 .. m.length) {
    (x += t * y[i]) %= m0;
    (t *= m[i]) %= m0;
  }
  return x;
}


enum MOO = 100_000_000_000_000_007L;
enum MOS = [17, 9920467, 592951213];

int N, M;
int[] X;

void main() {
  try {
    for (; ; ) {
      N = readInt() - 1;
      M = readInt();
      X = new int[M];
      foreach (m; 0 .. M) {
        X[m] = readInt();
      }
      
      debug {
        auto brute = new long[N + 1];
        brute[0] = 1;
        foreach (n; 1 .. N + 1) {
          foreach (x; X) {
            if (n >= x) {
              (brute[n] += brute[n - x]) %= MOO;
            }
          }
        }
        writeln("brute[N] = ", brute[N]);
      }
      
      /*
        0
        1
        
        01
        2
        
        01
        23
        
        012
        34
        
        012
        345
      */
      const lim = N / 2 + 1;
      int[] xs, ys;
      foreach (m; 0 .. M) {
        ((X[m] < lim) ? xs : ys) ~= X[m];
      }
      
      auto anss = new long[MOS.length];
      auto dp = new int[lim];
      foreach (h, MO; MOS) {
        dp[] = 0;
        dp[0] = 1;
        foreach (n; 0 .. lim) {
          foreach (x; xs) {
            if (n >= x) {
              if ((dp[n] += dp[n - x]) >= MO) {
                dp[n] -= MO;
              }
            }
          }
        }
        foreach (y; ys) {
          foreach (n; 0 .. lim) {
            if (N - y >= n) {
              (anss[h] += cast(long)(dp[n]) * dp[N - y - n]) %= MO;
            }
          }
        }
        foreach (n; lim .. N + 1) {
          dp[n - lim] = 0;
          foreach (x; xs) {
            if (n >= x) {
              if ((dp[n - lim] += dp[(n - x < lim) ? (n - x) : (n - x - lim)]) >= MO) {
                dp[n - lim] -= MO;
              }
            }
          }
        }
        if ((anss[h] += dp[N - lim]) >= MO) {
          anss[h] -= MO;
        }
      }
      debug {
        writeln(anss);
      }
      const ans = garner(anss, MOS.to!(long[]), MOO);
      writeln(ans);
    }
  } catch (EOFException e) {
  }
}