結果

問題 No.1956 猫の額
ユーザー NyaanNyaanNyaanNyaan
提出日時 2022-05-23 22:03:02
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 8,519 ms / 10,000 ms
コード長 4,204 bytes
コンパイル時間 1,949 ms
コンパイル使用メモリ 122,304 KB
実行使用メモリ 14,464 KB
最終ジャッジ日時 2024-09-20 14:07:19
合計ジャッジ時間 97,156 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 8,519 ms
14,208 KB
testcase_01 AC 472 ms
14,208 KB
testcase_02 AC 8,456 ms
14,208 KB
testcase_03 AC 590 ms
14,336 KB
testcase_04 AC 8,459 ms
14,464 KB
testcase_05 AC 7,644 ms
14,208 KB
testcase_06 AC 8,440 ms
14,208 KB
testcase_07 AC 3,515 ms
14,208 KB
testcase_08 AC 6,645 ms
13,952 KB
testcase_09 AC 891 ms
14,208 KB
testcase_10 AC 5,824 ms
13,824 KB
testcase_11 AC 2,838 ms
13,440 KB
testcase_12 AC 4,910 ms
13,568 KB
testcase_13 AC 95 ms
12,928 KB
testcase_14 AC 974 ms
12,800 KB
testcase_15 AC 489 ms
14,208 KB
testcase_16 AC 6,869 ms
14,208 KB
testcase_17 AC 412 ms
14,208 KB
testcase_18 AC 1,248 ms
14,336 KB
testcase_19 AC 4,662 ms
14,336 KB
testcase_20 AC 4,641 ms
14,208 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/**
 *  date : 2022-05-23 22:02:59
 */

#define NDEBUG

#include <algorithm>

#include <cassert>

#include <tuple>

#include <utility>

#include <vector>


using i128 = __int128_t;

namespace atcoder {

namespace internal {

// @param m `1 <= m`
// @return x mod m
constexpr i128 safe_mod(i128 x, i128 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
constexpr std::pair<i128, i128> inv_gcd(i128 a, i128 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
  i128 s = b, t = a;
  i128 m0 = 0, m1 = 1;

  while (t) {
    i128 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};
}

}  // namespace internal

}  // namespace atcoder

namespace atcoder {

i128 inv_mod(i128 x, i128 m) {
  assert(1 <= m);
  auto z = internal::inv_gcd(x, m);
  assert(z.first == 1);
  return z.second;
}

// (rem, mod)
std::pair<i128, i128> crt(const std::vector<i128>& r,
                          const std::vector<i128>& m) {
  assert(r.size() == m.size());
  int n = int(r.size());
  // Contracts: 0 <= r0 < m0
  i128 r0 = 0, m0 = 1;
  for (int i = 0; i < n; i++) {
    assert(1 <= m[i]);
    i128 r1 = internal::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)
    i128 g, im;
    std::tie(g, im) = internal::inv_gcd(m0, m1);

    i128 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)
    i128 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



#include <chrono>

#include <cstring>

#include <iomanip>

#include <iostream>

#include <map>

#include <numeric>

#include <queue>

#include <random>

#include <set>

#include <string>



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[92][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, 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;
    }
  }
  rep1(i, S) res[i] = dp[C][i];
}

int main() {
  scanf("%d %d %d\n", &N, &mod, &C);
  rep(i, N) scanf("%d", &a[i]);
  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 : {
           2,  3,  5,  7,  11, 13, 17, 19, 23, 29, 31,
           37, 41, 43, 47, 53, 59, 61, 67, 71, 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