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

提出ソース
結果

問題	No.2798 Multiple Chain
ユーザー	nana
提出日時	2025-01-30 11:41:44
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	4 ms / 2,000 ms
コード長	13,311 bytes
コンパイル時間	12,014 ms
コンパイル使用メモリ	649,668 KB
実行使用メモリ	6,820 KB
最終ジャッジ日時	2025-01-30 11:41:58
合計ジャッジ時間	13,199 ms
ジャッジサーバーID （参考情報）	judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 51
権限があれば一括ダウンロードができます
ソースコード

raw source code
#ifndef ONLINE_JUDGE
#define _GLIBCXX_DEBUG
#endif
#include "atcoder/all"
#include <string>
#include <bits/stdc++.h>
#include <climits>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/rational.hpp>
#include <boost/functional/hash.hpp>
// 任意長整数型
using Bint = boost::multiprecision::cpp_int;
// 仮数部が10進数で1024桁の浮動小数点数型(TLEしたら小さくする)
using BReal =
    boost::multiprecision::number<boost::multiprecision::cpp_dec_float<1024>>;
using Rat = boost::rational<Bint>;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <concepts>
#include <functional>
using namespace std;
using namespace __gnu_pbds;
// 型エイリアスの設定
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using namespace atcoder;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> inline bool chmin(T &a, T b) { return ((a>b) ? (a = b, true) : (false));}
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define REP(i,s,n) for(int i=s;i<(int)n;i++)
#define DREP(i,s,n) for(int i=n-1;i>=s;i--)
const long long inf = 1LL<<60;
const int infi = 1e9+1;
typedef long long ll;
typedef long double ld;
typedef __int128_t l3;
//cmpArg := 偏角ソート, atan2l(y, x); atan2l(y, x) = [-pi, pi]
#define cmpArg [](const auto &p1, const auto &p2) { return atan2l(p1.second, p1.first) < atan2l(p2.second, p2.first); }
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef unsigned long long ull;
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vm vector<mint>
#define vvm vector<vector<mint>>
#define vvc vector<vector<char>>
#define vc vector<char>
#define vvpi vector<vector<pi>>
#define vpi vector<pi>
#define vpl vector<pl>
#define vvpl vector<vector<pl>>
#define pb push_back
#define eb emplace_back
#define YES cout<<"Yes"<<endl;
#define NO cout<<"No"<<endl;
#define YN { cout << "Yes" << endl; } else { cout << "No" << endl; }
#define all(x) x.begin(), x.end()
#define rall(i) std::rbegin(i), std::rend(i)
#define len(x) ((ll)(x).size())
#define fi first
#define se second
#define UNIQUE(x) sort(all(x)), x.erase(unique(all(x)), x.end())
int pc(ll x) { return __builtin_popcount(x); } //ビット列にどれだけ1がたっているかを求める pop count
void cincout(){  ios::sync_with_stdio(false);   std::cin.tie(nullptr);  cout<< fixed << setprecision(15);  }
bool out_grid(ll i, ll j, ll h, ll w) { return (!(0<=i && i<h && 0<=j && j<w)); }
inline void read(int &a) { std::cin >> a; }
inline void read(unsigned &a) { std::cin >> a; }
inline void read(long &a) { std::cin >> a; }
inline void read(long long &a) { std::cin >> a; }
inline void read(unsigned long long &a) { std::cin >> a; }
inline void read(char &a) { std::cin >> a; }
inline void read(float &a) { std::cin >> a; }
inline void read(double &a) { std::cin >> a; }
inline void read(long double &a) { std::cin >> a; }
inline void read(std::vector<bool> &vec) {
    for (int32_t i = 0; i < vec.size(); i++) {
        int a;
        read(a);
        vec[i] = a;
    }
}
inline void read(std::string &a) { std::cin >> a; }
template <class T>
inline void read(std::vector<T> &vec);
template <class T, size_t size>
inline void read(std::array<T, size> &vec);
template <class T, class L>
inline void read(std::pair<T, L> &p);
template <class T, size_t size>
inline void read(T (&vec)[size]);
template <class T>
inline void read(std::vector<T> &vec) {
    for (auto &i : vec) read(i);
}
template <class T>
inline void read(std::deque<T> &vec) {
    for (auto &i : vec) read(i);
}
template <class T, size_t size>
inline void read(std::array<T, size> &vec) {
    for (auto &i : vec) read(i);
}
template <class T, class L>
inline void read(std::pair<T, L> &p) {
    read(p.first);
    read(p.second);
}
template <class T, size_t size>
inline void read(T (&vec)[size]) {
    for (auto &i : vec) read(i);
}
template <class T>
inline void read(T &a) {
    std::cin >> a;
}
inline void in() {}
template <class Head, class... Tail>
inline void in(Head &head, Tail &...tail) {
    read(head);
    in(tail...);
}
inline void print() { std::cout << ' '; }
inline void print(const bool &a) { std::cout << a; }
inline void print(const int &a) { std::cout << a; }
inline void print(const unsigned &a) { std::cout << a; }
inline void print(const long &a) { std::cout << a; }
inline void print(const long long &a) { std::cout << a; }
inline void print(const unsigned long long &a) { std::cout << a; }
inline void print(const char &a) { std::cout << a; }
inline void print(const char a[]) { std::cout << a; }
inline void print(const float &a) { std::cout << a; }
inline void print(const double &a) { std::cout << a; }
inline void print(const long double &a) { std::cout << a; }
inline void print(const std::string &a) {
    for (auto &&i : a) print(i);
}
template <class T>
inline void print(const std::vector<T> &vec);
template <class T, size_t size>
inline void print(const std::array<T, size> &vec);
template <class T, class L>
inline void print(const std::pair<T, L> &p);
template <class T, size_t size>
inline void print(const T (&vec)[size]);
template <class T>
inline void print(const std::vector<T> &vec) {
    if (vec.empty()) return;
    print(vec[0]);
    for (auto i = vec.begin(); ++i != vec.end();) {
        std::cout << ' ';
        print(*i);
    }
}
template <class T>
inline void print(const std::deque<T> &vec) {
    if (vec.empty()) return;
    print(vec[0]);
    for (auto i = vec.begin(); ++i != vec.end();) {
        std::cout << ' ';
        print(*i);
    }
}
template <class T, size_t size>
inline void print(const std::array<T, size> &vec) {
    print(vec[0]);
    for (auto i = vec.begin(); ++i != vec.end();) {
        std::cout << ' ';
        print(*i);
    }
}
template <class T, class L>
inline void print(const std::pair<T, L> &p) {
    print(p.first);
    std::cout << ' ';
    print(p.second);
}
template <class T, size_t size>
inline void print(const T (&vec)[size]) {
    print(vec[0]);
    for (auto i = vec; ++i != end(vec);) {
        std::cout << ' ';
        print(*i);
    }
}
template <class T>
inline void print(const T &a) {
    std::cout << a;
}
inline void out() { std::cout << '\n'; }
template <class T>
inline void out(const T &t) {
    print(t);
    std::cout << '\n';
}
template <class Head, class... Tail>
inline void out(const Head &head, const Tail &...tail) {
    print(head);
    std::cout << ' ';
    out(tail...);
}
#define vec(type, name, ...) vector<type> name(__VA_ARGS__);
#define vv(type, name, h, ...) std::vector<std::vector<type>> name(h, std::vector<type>(__VA_ARGS__));
#define INT(...) int32_t __VA_ARGS__; in(__VA_ARGS__)
#define LL(...) int64_t __VA_ARGS__; in(__VA_ARGS__)
#define ULL(...) uint64_t __VA_ARGS__; in(__VA_ARGS__)
#define STR(...) std::string __VA_ARGS__; in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__; in(__VA_ARGS__)
#define LD(...) long double __VA_ARGS__; in(__VA_ARGS__)
#define VEC(type, name, size) std::vector<type> name(size); in(name)
#define VV(type, name, h, w) std::vector<std::vector<type>> name(h, std::vector<type>(w)); in(name)
template <class T>
ll sum(const T &a) {
    return accumulate(std::begin(a), std::end(a), 0LL);
}
template <class T>
ld dsum(const T &a) {
    return accumulate(std::begin(a), std::end(a), 0.0L);
}
template <class T>
auto min(const T &a) {
    return *min_element(std::begin(a), std::end(a));
}
template <class T>
auto max(const T &a) {
    return *max_element(std::begin(a), std::end(a));
}
template<typename T> T floor_div(const T n, const T d) {
    assert(d != 0);
    return n / d - static_cast<T>((n ^ d) < 0 && n % d != 0);
}
template<typename T> T ceil_div(const T n, const T d) {
    assert(d != 0);
    return n / d + static_cast<T>((n ^ d) >= 0 && n % d != 0);
}

using mint = modint998244353;

namespace asalib {
  namespace math {
    template<typename T>
    constexpr bool miller_rabin_test(T n) {
      if (n < 2) [[unlikely]]
        return false;
      if (n % 2 == 0) return n == 2;
      T d = n - 1, s = 0;
      while (d % 2 == 0) d >>= 1, ++s;
      assert(d % 2 == 1);

      static_assert(sizeof(T) == 4 || sizeof(T) == 8, "T must be 32-bit or 64-bit integer type");
      constexpr bool is_64bit = sizeof(T) == 8;

      function<T(T, T, T)> modpow = [&](T a, T n, T mod) {
        T res = 1;
        while (n) {
          if constexpr (is_64bit) {
            if (n & 1) res = (__uint128_t) res * a % mod;
            a = (__uint128_t) a * a % mod;
          }
          else {
            if (n & 1) res = (unsigned long long) res * a % mod;
            a = (unsigned long long) a * a % mod;
          }
          n >>= 1;
        }
        return res;
      };

      function<bool(T)> test = [&](T a) {
        T x = modpow(a, d, n);
        if (x == 0) [[unlikely]]
          return false;
        if (x == 1) [[unlikely]]
          return true;
        for (T _ = 0; _ < s; ++_) {
          T y;
          if constexpr (is_64bit)
            y = (__uint128_t) x * x % n;
          else
            y = (unsigned long long) x * x % n;
          if (y == 1 && x != 1 && x != n - 1) return false;
          x = y;
        }
        return x == 1;
      };

      function<bool(vector<T>)> tests = [&](vector<T> basis) {
        for (T a : basis)
          if (!test(a)) return false;
        return true;
      };

      if (n < 2'047) return test(2);
      if (n < 1'373'653) return tests({ 2, 3 });
      if (n < 9'080'191) return tests({ 31, 73 });
      if (n < 25'326'001) return tests({ 2, 3, 5 });
      if (n < 3'215'031'751) return tests({ 2, 3, 5, 7 });
      if (n < 4'759'123'141) return tests({ 2, 7, 61 });
      if (n < 1'122'004'669'633) return tests({ 2, 13, 23, 1662803 });
      if (n < 2'152'302'898'747) return tests({ 2, 3, 5, 7, 11 });
      if (n < 3'474'749'660'383) return tests({ 2, 3, 5, 7, 11, 13 });
      if (n < 341'550'071'728'321) return tests({ 2, 3, 5, 7, 11, 13, 17 });
      if (n < 3'825'123'056'546'413'051) return tests({ 2, 3, 5, 7, 11, 13, 17, 19, 23 });
      if (ull(n) <= 18'446'744'073'709'551'615ULL) return tests({ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 });
      // 18'446'744'073'709'551'616 は 2^64 であり、これ以上の数は 64 ビット整数型では表現できない
      // TODO: 多倍長整数を使う場合は if を追加する
      // TODO: C++23 以降なら __builtin_unreachable() -> std::unreachable() に変更可能
      __builtin_unreachable();
    }
  }  // namespace math
}  // namespace asalib

namespace asalib {
  namespace math {
    template<typename T>
    constexpr vector<pair<T, T>> pollards_rho(T n) {
      if (n < 2) [[unlikely]]
        return {};

      vector<pair<T, T>> res(0);
      // ある程度小さい素因数については前もって素因数分解しておく
      for (T i = 2; i * i <= min((T) 10000, n); ++i) {
        if (n % i == 0) {
          T e = 0;
          while (n % i == 0) n /= i, ++e;
          res.push_back({ i, e });
        }
      }
      if (n == 1) [[unlikely]]
        return res;

      // ここからメイン
      static_assert(sizeof(T) == 4 || sizeof(T) == 8, "T must be 32-bit or 64-bit integer type");
      constexpr bool is_64bit = sizeof(T) == 8;
      auto f = [&](T x, T s) -> T {
        if constexpr (is_64bit) return ((__uint128_t) x * x + s) % n;
        else
          return ((unsigned long long) x * x + s) % n;
      };
      function<void(T&, T)> rho = [&](T& n, T cnt) {
        if (n == 1) [[unlikely]]
          return;
        if (miller_rabin_test(n)) {
          res.push_back({ n, cnt });
          n = 1;
          return;
        }
        T s = 0;
        while (true) {
          T x = ++s, y = f(x, s);
          while (true) {
            T p = gcd(y - x + n, n);
            if (p == 0 || p == n) break;  // 失敗、 seed 変えてやり直し
            if (p != 1) {
              assert(n % p == 0);
              T e = 0;
              while (n % p == 0) n /= p, ++e;
              rho(p, cnt * e);
              if (n > 1) rho(n, cnt);
              return;
            }
            x = f(x, s), y = f(f(y, s), s);
          }
        }
      };
      while (n > 1) rho(n, 1);

      sort(res.begin(), res.end());
      return res;
    }
  }  // namespace math
}  // namespace asalib

int main()
{
    LL(N);
    auto pf = asalib::math::pollards_rho<ll>(N); //素因数分解
    //分割数
    const int maxi = 100;
    vvl dp(maxi+1,vl(maxi+1,0)); dp[0][0] = 1;
    rep(i,maxi) rep(j,maxi) {
        dp[i+1][j+1] += dp[i][j];
        if(i+j<=maxi) dp[i+j][j] += dp[i][j];
    }
    rep(i,maxi+1) rep(j,maxi) dp[i][j+1] += dp[i][j];
    ll ema = -1;
    for(auto [p,e] : pf) chmax(ema, e);
    //各素因数(p,e)に対してdp[e][*]を使用できる
    ll ans = 0;
    for(int length = 1;length <= ema; length++) {
        //length以下をとる - length-1以下をとる
        ll r = 1, l = 1;
        for(auto [p,e] : pf) {
            r *= dp[e][length];
            l *= dp[e][length-1];
        }
        ans += r - l;
    }
    out(ans);
}
yukicoder

結果

ソースコード
