#991504 (C++23) No.2798 Multiple Chain

提出ソース

結果

問題	No.2798 Multiple Chain
ユーザー	Misuki
提出日時	2024-06-28 22:15:04
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	3 ms / 2,000 ms
コード長	6,524 bytes
コンパイル時間	2,820 ms
コンパイル使用メモリ	216,936 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-06-28 22:15:15
合計ジャッジ時間	4,262 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	3 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	2 ms 5,376 KB
testcase_16	AC	2 ms 5,376 KB
testcase_17	AC	1 ms 5,376 KB
testcase_18	AC	3 ms 5,376 KB
testcase_19	AC	2 ms 5,376 KB
testcase_20	AC	2 ms 5,376 KB
testcase_21	AC	2 ms 5,376 KB
testcase_22	AC	2 ms 5,376 KB
testcase_23	AC	2 ms 5,376 KB
testcase_24	AC	2 ms 5,376 KB
testcase_25	AC	3 ms 5,376 KB
testcase_26	AC	2 ms 5,376 KB
testcase_27	AC	2 ms 5,376 KB
testcase_28	AC	2 ms 5,376 KB
testcase_29	AC	2 ms 5,376 KB
testcase_30	AC	2 ms 5,376 KB
testcase_31	AC	2 ms 5,376 KB
testcase_32	AC	2 ms 5,376 KB
testcase_33	AC	2 ms 5,376 KB
testcase_34	AC	2 ms 5,376 KB
testcase_35	AC	2 ms 5,376 KB
testcase_36	AC	2 ms 5,376 KB
testcase_37	AC	2 ms 5,376 KB
testcase_38	AC	2 ms 5,376 KB
testcase_39	AC	2 ms 5,376 KB
testcase_40	AC	2 ms 5,376 KB
testcase_41	AC	2 ms 5,376 KB
testcase_42	AC	3 ms 5,376 KB
testcase_43	AC	2 ms 5,376 KB
testcase_44	AC	2 ms 5,376 KB
testcase_45	AC	2 ms 5,376 KB
testcase_46	AC	2 ms 5,376 KB
testcase_47	AC	2 ms 5,376 KB
testcase_48	AC	2 ms 5,376 KB
testcase_49	AC	2 ms 5,376 KB
testcase_50	AC	2 ms 5,376 KB
testcase_51	AC	2 ms 5,376 KB
testcase_52	AC	2 ms 5,376 KB
testcase_53	AC	2 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#pragma GCC optimize("O2")
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cfenv>
#include <cfloat>
#include <chrono>
#include <cinttypes>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdarg>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <initializer_list>
#include <iomanip>
#include <ios>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <streambuf>
#include <string>
#include <tuple>
#include <type_traits>
#include <variant>
#include <bit>
#include <compare>
#include <concepts>
#include <numbers>
#include <ranges>
#include <span>

//#define int ll
#define INT128_MAX (__int128)(((unsigned __int128) 1 << ((sizeof(__int128) * __CHAR_BIT__) - 1)) - 1)
#define INT128_MIN (-INT128_MAX - 1)

#define clock chrono::steady_clock::now().time_since_epoch().count()

#ifdef DEBUG
#define dbg(x) cout << (#x) << " = " << (x) << '\n'
#else
#define dbg(x)
#endif

using namespace std;

template<ranges::forward_range rng, class T = ranges::range_value_t<rng>, class OP = plus<T>>
void pSum(rng &&v) {
  if (!v.empty())
    for(T p = v[0]; T &x : v | views::drop(1))
      x = p = OP()(p, x);
}
template<ranges::forward_range rng, class T = ranges::range_value_t<rng>, class OP>
void pSum(rng &&v, OP op) {
  if (!v.empty())
    for(T p = v[0]; T &x : v | views::drop(1))
      x = p = op(p, x);
}
template<class T>
T floorDiv(T a, T b) {
  if (b < 0) a *= -1, b *= -1;
  return a >= 0 ? a / b : (a - b + 1) / b;
}
template<class T>
T ceilDiv(T a, T b) {
  if (b < 0) a *= -1, b *= -1;
  return a >= 0 ? (a + b - 1) / b : a / b;
}

template<class T>
ostream& operator<<(ostream& os, const pair<T, T> pr) {
  return os << pr.first << ' ' << pr.second;
}
template<class T, size_t N>
ostream& operator<<(ostream& os, const array<T, N> &arr) {
  for(const T &X : arr)
    os << X << ' ';
  return os;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T> &vec) {
  for(const T &X : vec)
    os << X << ' ';
  return os;
}
template<class T>
ostream& operator<<(ostream& os, const set<T> &s) {
  for(const T &x : s)
    os << x << ' ';
  return os;
}

#define rep(i, a, b) for (int i = int(a); i < int(b); i++)
#define trav(a, x) for (auto& a : x)
#define per(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define all(x) x.begin(), x.end()

template <class T> int sz(T&& a) { return int(size(forward<T>(a))); }

template <class T> using vc = vector<T>;
template <class T> using vvc = vc<vc<T>>;

using ll = int64_t;
using vi = vc<int>;
using pii = pair<int, int>;
using uint = uint32_t;
using ull = uint64_t;

mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());

template <class F>
struct ycr {
	F f;
	template <class T> explicit ycr(T&& f_) : f(forward<T>(f_)) {}

	template <class... Args> decltype(auto) operator()(Args&&... args) {
		return f(ref(*this), forward<Args>(args)...);
	}
};
template <class F> decltype(auto) yc(F&& f) {
	return ycr<decay_t<F>>(forward<F>(f));
}

// Reference: https://judge.yosupo.jp/submission/110118
struct montgomery {
	using T = ull;
	using u128 = __uint128_t;
	T n, n2, r, t, e;
	montgomery(T n_) : n(n_) {
		assert(n < (T(1) << 62));
		assert(n % 2 == 1);
		n2 = n * 2;
		r = n & 3;
		rep(_,0,5) r *= 2-n*r;
		r = -r;
		assert(r * n == T(-1));
		t = -T(n) % n;
		e = T(-u128(n) % n);
	}

	T reduce(u128 a) const {
		return T((a + u128(T(a) * r) * n) >> 64);
	}
	T mult(T a, T b) const {
		return reduce(u128(a) * b);
	}

	T encode(T a) const {
		return mult(a, e);
	}
	T decode(T a) const {
		a = reduce(a);
		return a < n ? a : a-n;
	}

	T pow(T a, ll b) const {
		assert(b >= 0);
		T v = t;
		while (b) {
			if (b & 1) v = mult(v, a);
			a = mult(a, a);
			b >>= 1;
		}
		return v;
	}

	bool is_prime() const {
		assert(n >= 3);
		assert(n & 1);

		T d = n-1;
		int s = __builtin_ctzll(d);
		d >>= s;

		auto check = [&](T a) -> int {
			a %= n;
			if (a == 0) return 1;
			T p = pow(encode(a), d);
			if (decode(p) == 1 || decode(p) == n-1) return 0;
			for (int z = 0; z < s; z++) {
				p = mult(p, p);
				if (decode(p) == n-1) return 0;
			}
			return -1;
		};

		for (T a : {2,325,9375,28178,450775,9780504,1795265022}) {
			int w = check(a);
			if (w) return w == 1;
		}
		return true;
	}

	ull pollard() const {
		assert(n >= 3);
		assert(n & 1);

		if (is_prime()) return n;

		while (true) {
			T c = mt() % (n-1) + 1;
			T y = mt() % (n-1) + 1;
			auto f = [&](T a) -> T {
				return reduce(u128(a) * a + c);
			};
			for (T s = 1; ; s *= 2) {
				T x = n2-y;
				T m = min(T(1) << (__lg(n)/6), s);
				rep(i,0,s/m) {
					T w = t, z = y;
					rep(j,0,m) {
						y = f(y);
						w = mult(w, y+x);
					}
					T g = __gcd(decode(w), n);
					if (g != 1) {
						if (g < n) return g;
						rep(j,0,m) {
							z = f(z);
							if ((g = __gcd(decode(z+x), n)) != 1) {
								if (g < n) return g;
								goto fail;
							}
						}
						assert(false);
					}
				}
			}
fail:;
		}
	}
};

using ull = uint64_t;
bool is_prime(ull n) {
	if (n <= 1) return false;
	if (n == 2) return true;
	if (n % 2 == 0) return false;
	return montgomery(n).is_prime();
}

ull get_divisor(ull n) {
	assert(n > 1);
	if (n % 2 == 0) return 2;
	return montgomery(n).pollard();
}

vc<ull> factorize(ull n) {
	vc<ull> res;
	yc([&](auto self, ull v) -> void {
		if (v == 1) return;
		ull d = get_divisor(v);
		if (d == v) {
			res.push_back(d);
			return;
		}
		self(d);
		self(v/d);
	})(n);
	return res;
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(NULL);

  ull n; cin >> n;
  map<int, int> m;
  for(auto x : factorize(n)) m[x]++;

  int mxL = 0;
  for(auto [_, f] : m) mxL = max(mxL, f);

  int ans = 0;
  for(int l = 1; l <= mxL; l++) {
    array<int, 2> cnt = {1, 0};
    for(auto [_, f] : m) {
      vector dp(l + 1, vector(2, vector<int>(f + 1)));
      dp[0][0][f] = cnt[0], dp[0][1][f] = cnt[1];
      for(int i = 0; i < l; i++) for(int j : {0, 1}) for(int k = 0; k <= f; k++) {
        for(int r = 0; k - r * (i + 1) >= 0; r++)
          dp[i + 1][j | (r != 0 and i + 1 == l)][k - r * (i + 1)] += dp[i][j][k];
      }
      cnt[0] = dp[l][0][0], cnt[1] = dp[l][1][0];
    }
    ans += cnt[1];
  }

  cout << ans << '\n';

  return 0;
}

yukicoder

結果

テストケース

ソースコード