結果

問題 No.695 square1001 and Permutation 4
ユーザー ei1333333ei1333333
提出日時 2018-06-09 02:29:52
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,190 ms / 7,000 ms
コード長 2,513 bytes
コンパイル時間 2,548 ms
コンパイル使用メモリ 211,292 KB
実行使用メモリ 42,688 KB
最終ジャッジ日時 2024-07-22 19:24:44
合計ジャッジ時間 16,981 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 193 ms
42,688 KB
testcase_01 AC 675 ms
42,632 KB
testcase_02 AC 127 ms
42,488 KB
testcase_03 AC 120 ms
42,412 KB
testcase_04 AC 933 ms
42,480 KB
testcase_05 AC 869 ms
42,388 KB
testcase_06 AC 1,053 ms
42,484 KB
testcase_07 AC 1,392 ms
42,500 KB
testcase_08 AC 996 ms
42,556 KB
testcase_09 AC 878 ms
42,488 KB
testcase_10 AC 669 ms
42,516 KB
testcase_11 AC 2,189 ms
42,516 KB
testcase_12 AC 1,585 ms
42,472 KB
testcase_13 AC 2,190 ms
42,496 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

const int64 mod = 100000000000000007;

// 人生ね

using lll = __int128_t;

std::pair< lll, lll > crt(lll a1, lll m1, lll a2, lll m2) {
  auto normal = [](lll x, lll m) { return x >= -x ? x % m : m - (-x) % m; };
  auto modmul = [&normal](lll a, lll b, lll m) { return normal(a, m) * normal(b, m) % m; };
  auto extgcd = [](lll a, lll b, lll &x, lll &y) {
    for(lll u = y = 1, v = x = 0; a;) {
      lll q = b / a;
      std::swap(x -= q * u, u);
      std::swap(y -= q * v, v);
      std::swap(b -= q * a, a);
    }
    return b;
  };
  lll k1, k2;
  lll g = extgcd(m1, m2, k1, k2);
  if(normal(a1, g) != normal(a2, g))
    return std::make_pair(-1, -1);
  else {
    lll l = m1 / g * m2;
    lll x = a1 + modmul(modmul((a2 - a1) / g, k1, l), m1, l);
    return std::make_pair(x, l);
  }
}

std::pair< lll, lll > crt(std::vector< lll > a, std::vector< lll > m) {
  lll mod = 1, ans = 0;
  int n = a.size();
  for(int i = 0; i < n; i++) {
    std::tie(ans, mod) = crt(ans, mod, a[i], m[i]);
    if(ans == -1) return std::make_pair(-1, -1);
  }
  return std::make_pair(ans, mod);
}

int N, M;
int dp[10000000];
vector< lll > mods = {17*9920467, 592951213};
vector< int > large, small;

int main() {
  cin >> N >> M;
  for(int i = 0; i < M; i++) {
    int v;
    cin >> v;
    if(v >= 10000000) large.emplace_back(v); // えーこれだったら人生なので
    else small.emplace_back(v);
  }
  vector< lll > anss;

  for(int _ = 0; _ < 2; _++) {
    int64 ret = 0;

    memset(dp, 0, sizeof(dp));

    dp[0] = 1;
    for(int k = 0; k < 10000000; k++) {
      for(int i = 0; i < small.size(); i++) {
        if(k - small[i] >= 0) {
          dp[k] += dp[k - small[i]];
          if(dp[k] >= mods[_]) dp[k] -= mods[_];
        }
      }
    }

    for(int k = 0; k < N; k++) {
      for(int i = 0; i < large.size(); i++) {
        if(k + large[i] < N) {
          ret += 1LL * dp[k] * dp[N - (large[i] + k) - 1] % mods[_];
          ret %= mods[_];
        }
      }
    }


    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for(int k = 1; k < N; k++) {
      int64 v = 0;
      for(int i = 0; i < small.size(); i++) {
        if(k - small[i] >= 0) {
          v += dp[(k - small[i] + 10000000) % 10000000];
          if(v >= mods[_]) v -= mods[_];
        }
      }
      dp[k % 10000000] = v;
    }

    anss.emplace_back((ret + dp[(N + 10000000 - 1) % 10000000]) % mods[_]);
  }

  cout << (int64) crt(anss, mods).first << endl;

}
0