結果

問題 No.1956 猫の額
ユーザー NyaanNyaanNyaanNyaan
提出日時 2022-05-23 22:47:47
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3,309 ms / 10,000 ms
コード長 4,118 bytes
コンパイル時間 1,236 ms
コンパイル使用メモリ 125,448 KB
実行使用メモリ 9,972 KB
最終ジャッジ日時 2023-10-20 18:31:49
合計ジャッジ時間 42,148 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3,299 ms
9,972 KB
testcase_01 AC 373 ms
9,972 KB
testcase_02 AC 3,299 ms
9,972 KB
testcase_03 AC 449 ms
9,972 KB
testcase_04 AC 3,293 ms
9,972 KB
testcase_05 AC 3,039 ms
9,972 KB
testcase_06 AC 3,309 ms
9,972 KB
testcase_07 AC 2,179 ms
9,972 KB
testcase_08 AC 2,631 ms
9,972 KB
testcase_09 AC 658 ms
9,972 KB
testcase_10 AC 2,309 ms
9,972 KB
testcase_11 AC 1,340 ms
9,972 KB
testcase_12 AC 1,945 ms
9,972 KB
testcase_13 AC 75 ms
9,628 KB
testcase_14 AC 372 ms
9,476 KB
testcase_15 AC 381 ms
9,972 KB
testcase_16 AC 2,733 ms
9,972 KB
testcase_17 AC 328 ms
9,972 KB
testcase_18 AC 634 ms
9,972 KB
testcase_19 AC 1,879 ms
9,972 KB
testcase_20 AC 1,875 ms
9,972 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/**
 *  date : 2022-05-23 22:47:43
 */

#define NDEBUG
#include <algorithm>

#include <cassert>

#include <chrono>

#include <cstring>

#include <iomanip>

#include <iostream>

#include <map>

#include <numeric>

#include <queue>

#include <random>

#include <set>

#include <string>

#include <utility>

#include <vector>



#include <tuple>

namespace atcoder {

// @param m `1 <= m`
// @return x mod m
template <typename T>
constexpr T safe_mod(T x, T m) {
  x %= m;
  if (x < 0) x += m;
  return x;
}

// @param b `1 <= b`
// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
template <typename T>
constexpr std::pair<T, T> inv_gcd(T a, T b) {
  a = safe_mod(a, b);
  if (a == 0) return {b, 0};

  // Contracts:
  // [1] s - m0 * a = 0 (mod b)
  // [2] t - m1 * a = 0 (mod b)
  // [3] s * |m1| + t * |m0| <= b
  T s = b, t = a;
  T m0 = 0, m1 = 1;

  while (t) {
    T u = s / t;
    s -= t * u;
    m0 -= m1 * u;  // |m1 * u| <= |m1| * s <= b

    // [3]:
    // (s - t * u) * |m1| + t * |m0 - m1 * u|
    // <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
    // = s * |m1| + t * |m0| <= b

    auto tmp = s;
    s = t;
    t = tmp;
    tmp = m0;
    m0 = m1;
    m1 = tmp;
  }
  // by [3]: |m0| <= b/g
  // by g != b: |m0| < b/g
  if (m0 < 0) m0 += b / s;
  return {s, m0};
}

template <typename T>
T inv_mod(T x, T m) {
  assert(1 <= m);
  auto z = inv_gcd(x, m);
  assert(z.first == 1);
  return z.second;
}

// (rem, mod)
template <typename T>
std::pair<T, T> crt(const std::vector<T>& r, const std::vector<T>& m) {
  assert(r.size() == m.size());
  int n = int(r.size());
  // Contracts: 0 <= r0 < m0
  T r0 = 0, m0 = 1;
  for (int i = 0; i < n; i++) {
    assert(1 <= m[i]);
    T r1 = safe_mod(r[i], m[i]), m1 = m[i];
    if (m0 < m1) {
      std::swap(r0, r1);
      std::swap(m0, m1);
    }
    if (m0 % m1 == 0) {
      if (r0 % m1 != r1) return {0, 0};
      continue;
    }
    // assume: m0 > m1, lcm(m0, m1) >= 2 * max(m0, m1)

    // (r0, m0), (r1, m1) -> (r2, m2 = lcm(m0, m1));
    // r2 % m0 = r0
    // r2 % m1 = r1
    // -> (r0 + x*m0) % m1 = r1
    // -> x*u0*g % (u1*g) = (r1 - r0) (u0*g = m0, u1*g = m1)
    // -> x = (r1 - r0) / g * inv(u0) (mod u1)

    // im = inv(u0) (mod u1) (0 <= im < u1)
    T g, im;
    std::tie(g, im) = inv_gcd(m0, m1);

    T u1 = (m1 / g);
    // |r1 - r0| < (m0 + m1) <= lcm(m0, m1)
    if ((r1 - r0) % g) return {0, 0};

    // u1 * u1 <= m1 * m1 / g / g <= m0 * m1 / g = lcm(m0, m1)
    T x = (r1 - r0) / g % u1 * im % u1;

    // |r0| + |m0 * x|
    // < m0 + m0 * (u1 - 1)
    // = m0 + m0 * m1 / g - m0
    // = lcm(m0, m1)
    r0 += x * m0;
    m0 *= u1;  // -> lcm(m0, m1)
    if (r0 < 0) r0 += m0;
  }
  return {r0, m0};
}
}  // namespace atcoder

using namespace std;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
#define repr(i, n) for (int i = (n)-1; i >= 0; i--)
using u8 = uint8_t;
using i128 = __int128_t;

u8 dp[46][100064];
u8 res[100064];
i128 ans[100064];
int a[92], N, mod, C, rui[92];

void calc(char M) {
  memset(dp, 0, sizeof(dp));
  dp[0][0] = 1;
  int S = accumulate(a, a + N, 0);
  rep(k, N) {
    int x = a[k];
    repr(i, min(45, N + 1)) rep(j, rui[k] + 1) {
      dp[i + 1][j + x] += dp[i][j];
      if (dp[i + 1][j + x] >= M) dp[i + 1][j + x] -= M;
    }
  }
  if (C <= 45) {
    rep1(i, S) res[i] = dp[C][i];
  } else {
    rep1(i, S) res[i] = dp[N - C][S - i];
  }
}

int main() {
  scanf("%d %d %d\n", &N, &mod, &C);
  rep(i, N) scanf("%d", &a[i]);
  sort(begin(a), begin(a) + N);
  rep(i, N) rui[i + 1] = a[i] + rui[i];
  int S = accumulate(a, a + N, 0);
  i128 curmod = 1;
  vector<i128> m(2), r(2);
  for (int p :
       {127, 126, 125, 121, 113, 109, 107, 103, 101, 97, 89, 83, 79, 73}) {
    m[0] = curmod, m[1] = p;
    calc(p);
    if (p == 2) {
      rep(i, S + 1) ans[i] = res[i];
      curmod = p;
      continue;
    }
    rep(i, S + 1) {
      r[0] = ans[i], r[1] = res[i];
      ans[i] = atcoder::crt(r, m).first;
    }
    curmod *= p;
  }
  rep1(i, S) {
    printf("%d", int(ans[i] % mod));
    printf(i == S ? "\n" : " ");
  }
}
0