結果

問題 No.695 square1001 and Permutation 4
ユーザー ei1333333ei1333333
提出日時 2018-06-08 23:48:39
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3,372 ms / 7,000 ms
コード長 2,515 bytes
コンパイル時間 5,899 ms
コンパイル使用メモリ 202,184 KB
最終ジャッジ日時 2025-01-05 11:03:44
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

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; _ < 3; _++) {
    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