結果
| 問題 | No.2075 GCD Subsequence |
| ユーザー |
 cureskol
|
| 提出日時 | 2024-11-06 23:50:28 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 851 ms / 4,000 ms |
| コード長 | 11,831 bytes |
| コンパイル時間 | 6,018 ms |
| コンパイル使用メモリ | 306,448 KB |
| 実行使用メモリ | 78,464 KB |
| 最終ジャッジ日時 | 2024-11-06 23:51:00 |
| 合計ジャッジ時間 | 30,804 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 28 |
ソースコード
#pragma region template#ifdef USE_PRECOMPILE#include "pch.h"#else#pragma GCC optimize("Ofast")#include <bits/stdc++.h>using namespace std;using ll = long long;using ld = long double;using vi = std::vector<int>;using vll = std::vector<ll>;template <typename T> using PA = std::pair<T, T>;using pi = PA<int>;using pll = PA<ll>;#define overload2(a, b, c, ...) c#define overload3(a, b, c, d, ...) d#define overload4(a, b, c, d, e, ...) e#define overload5(a, b, c, d, e, f, ...) f#define TYPE1(T) template <typename T>#define TYPE2(T, U) template <typename T, typename U>#define TYPE(...) overload2(__VA_ARGS__, TYPE2, TYPE1)(__VA_ARGS__)#define TYPES1(T) template <typename... T>#define TYPES2(H, T) template <typename H, typename... T>#define TYPES(...) overload2(__VA_ARGS__, TYPES2, TYPES1)(__VA_ARGS__)#define REP4(i, s, n, d) for (int i = (s); i < (n); i += (d))#define REP3(i, s, n) REP4(i, s, n, 1)#define REP2(i, n) REP3(i, 0, n)#define REP1(n) REP2(tomato, n)#define REP(...) overload4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__)#define RREP4(i, n, s, d) for (int i = (n) - 1; i >= (s); i -= (d))#define RREP3(i, n, s) RREP4(i, n, s, 1)#define RREP2(i, n) RREP3(i, n, 0)#define RREP1(n) RREP2(tomato, n)#define RREP(...) \overload4(__VA_ARGS__, RREP4, RREP3, RREP2, RREP1)(__VA_ARGS__)#define FOR4(a, b, c, d, v) for (auto [a, b, c, d] : v)#define FOR3(a, b, c, v) for (auto [a, b, c] : v)#define FOR2(a, b, v) for (auto [a, b] : v)#define FOR1(a, v) for (auto a : v)#define FOR(...) overload5(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)#define AFOR4(a, b, c, d, v) for (auto &[a, b, c, d] : v)#define AFOR3(a, b, c, v) for (auto &[a, b, c] : v)#define AFOR2(a, b, v) for (auto &[a, b] : v)#define AFOR1(a, v) for (auto &a : v)#define AFOR(...) \overload5(__VA_ARGS__, AFOR4, AFOR3, AFOR2, AFOR1)(__VA_ARGS__)#define CFOR4(a, b, c, d, v) for (const auto &[a, b, c, d] : v)#define CFOR3(a, b, c, v) for (const auto &[a, b, c] : v)#define CFOR2(a, b, v) for (const auto &[a, b] : v)#define CFOR1(a, v) for (const auto &a : v)#define CFOR(...) \overload5(__VA_ARGS__, CFOR4, CFOR3, CFOR2, CFOR1)(__VA_ARGS__)#define RFOR4(a, b, c, d, v) for (auto [a, b, c, d] : v | std::views::reverse)#define RFOR3(a, b, c, v) for (auto [a, b, c] : v | std::views::reverse)#define RFOR2(a, b, v) for (auto [a, b] : v | std::views::reverse)#define RFOR1(a, v) for (auto a : v | std::views::reverse)#define RFOR(...) \overload5(__VA_ARGS__, RFOR4, RFOR3, RFOR2, RFOR1)(__VA_ARGS__)#define RAFOR4(a, b, c, d, v) for (auto &[a, b, c, d] : v | std::views::reverse)#define RAFOR3(a, b, c, v) for (auto &[a, b, c] : v | std::views::reverse)#define RAFOR2(a, b, v) for (auto &[a, b] : v | std::views::reverse)#define RAFOR1(a, v) for (auto &a : v | std::views::reverse)#define RAFOR(...) \overload5(__VA_ARGS__, RAFOR4, RAFOR3, RAFOR2, RAFOR1)(__VA_ARGS__)#define RCFOR4(a, b, c, d, v) \for (const auto &[a, b, c, d] : v | std::views::reverse)#define RCFOR3(a, b, c, v) for (const auto &[a, b, c] : v | std::views::reverse)#define RCFOR2(a, b, v) for (const auto &[a, b] : v | std::views::reverse)#define RCFOR1(a, v) for (const auto &a : v | std::views::reverse)#define RCFOR(...) \overload5(__VA_ARGS__, RCFOR4, RCFOR3, RCFOR2, RCFOR1)(__VA_ARGS__)#define ALL(v) v.begin(), v.end()#define RALL(v) v.rbegin(), v.rend()#define SORT(v) std::ranges::sort(v)#define RSORT(v) sort(RALL(v))#define REVERSE(v) std::ranges::reverse(v)#define UNIQUE(v) SORT(v), v.erase(unique(ALL(v)), v.end())#define SZ(v) int(v.size())#define MAX(v) std::ranges::max(v)#define MIN(v) std::ranges::min(v)template <typename T>std::conditional_t<std::is_same_v<T, int>, ll, T> SUM(const std::vector<T> &v) {return std::accumulate(ALL(v), std::conditional_t<std::is_same_v<T, int>, ll, T>(0));}TYPES(T) void input(T &...a) { (std::cin >> ... >> a); }#define DECLARE(T, ...) \T __VA_ARGS__; \input(__VA_ARGS__);#define INT(...) DECLARE(int, __VA_ARGS__)#define STR(...) DECLARE(std::string, __VA_ARGS__)#define LL(...) DECLARE(long long, __VA_ARGS__)#define CHR(...) DECLARE(char, __VA_ARGS__)#define DBL(...) DECLARE(double, __VA_ARGS__)#define VI(n, v) \vi v(n); \std::cin >> v;#define VLL(n, v) \vll v(n); \std::cin >> v;#define VS(n, s) \std::vector<std::string> s(n); \std::cin >> s;TYPE(T, S) std::istream &operator>>(std::istream &is, std::pair<T, S> &p) {is >> p.first >> p.second;return is;}TYPE(T, S)std::ostream &operator<<(std::ostream &os, const std::pair<T, S> &p) {os << p.first << " " << p.second;return os;}TYPE(T) istream &operator>>(std::istream &is, std::vector<T> &v) {for (auto &a : v)std::cin >> a;return is;}TYPE(T) std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {if (&os == &std::cerr)os << "[";REP (i, v.size()) {os << v[i];if (i + 1 < v.size())os << (&os == &std::cerr ? "," : " ");}if (&os == &std::cerr)os << "]";return os;}#ifdef __DEBUG#include <debug>#else#define debug(...) void(0)#endifvoid print() { cout << '\n'; }TYPES(T, Ts) void print(const T &a, const Ts &...b) {std::cout << a;(std::cout << ... << (std::cout << ' ', b));std::cout << '\n';}TYPE(T) using pq = std::priority_queue<T>;TYPE(T) using pqg = std::priority_queue<T, std::vector<T>, std::greater<T>>;TYPE(T) T pick(std::queue<T> &que) {assert(que.size());T a = que.front();que.pop();return a;}TYPE(T) T pick(pq<T> &que) {assert(que.size());T a = que.top();que.pop();return a;}TYPE(T) T pick(pqg<T> &que) {assert(que.size());T a = que.top();que.pop();return a;}TYPE(T) T pick(std::stack<T> &sta) {assert(sta.size());T a = sta.top();sta.pop();return a;}TYPE(T) void clear(T &v) { v = decltype(v)(); }std::string YES(bool f = true) { return (f ? "YES" : "NO"); }std::string Yes(bool f = true) { return (f ? "Yes" : "No"); }std::string yes(bool f = true) { return (f ? "yes" : "no"); }constexpr int INF = 1e9 + 7;constexpr ll LINF = ll(1e18) + 7;constexpr ld EPS = 1e-10;vi iota(int n) {vi a(n);std::iota(ALL(a), 0);return a;}TYPE(T) void add(std::vector<T> &v, T a = 1) {AFOR (p, v)p += a;}TYPE(T) T rev(T a) {REVERSE(a);return a;}TYPE(T) void fin(T a) {std::cout << a << '\n';exit(0);}TYPE(T) bool chmax(T &a, T b) { return (a < b && (a = b, true)); }TYPE(T) bool chmin(T &a, T b) { return (a > b && (a = b, true)); }TYPES(T, Ns) auto make_vector(T x, int n, Ns... ns) {if constexpr (sizeof...(ns) == 0)return std::vector<T>(n, x);elsereturn std::vector(n, make_vector<T>(x, ns...));}bool in(const ll S, const int a) { return (S >> a) & 1; }int digit(char c) { return (c >= '0' and c <= '9' ? c - '0' : -1); }void signal_hander(int signal) { std::exit(EXIT_FAILURE); }#endif#pragma endregion template#include <atcoder/convolution>#include <atcoder/modint>using namespace atcoder;using mint = modint998244353;namespace atcoder {ostream &operator<<(ostream &os, mint a) {os << a.val();return os;}istream &operator>>(istream &is, mint &a) {long long b;is >> b;a = b;return is;}} // namespace atcodertemplate <int MAX, bool PRIME_FACTOR = false, bool DIVISOR = false>class PrimeUtil {using u32 = std::uint32_t;using u64 = std::uint64_t;using PF = std::vector<std::pair<u32, int>>;template <typename T> using ARR = std::array<T, MAX + 1>;template <typename T, bool F> using COND = std::conditional_t<F, T, bool>;ARR<bool> isP;public:std::vector<u32> primes;COND<ARR<PF>, PRIME_FACTOR> prime_factors;COND<ARR<std::vector<u32>>, DIVISOR> divisors; // 自明な約数は入らないstatic u64 pow2(u64 a) { return a * a; }public:PrimeUtil() {std::ranges::fill(isP, true);isP[0] = isP[1] = false;primes.reserve(MAX / 10);for (int i = 2; i <= MAX; i++) {if constexpr (DIVISOR) {for (int j = 2 * i; j <= MAX; j += i)divisors[j].push_back(i);}if (!isP[i])continue;primes.push_back(i);for (u64 j = pow2(i); j <= MAX; j += i)isP[j] = false;if constexpr (PRIME_FACTOR) {for (int j = i; j <= MAX; j += i)prime_factors[j].emplace_back(i, 1);int limit = MAX / i + 1;for (u64 j = pow2(i); j <= MAX; j *= i) {for (int k = j; k <= MAX; k += j)prime_factors[k].back().second++;if (j > limit)break;}}}}bool is_prime(u64 x) const {if (x <= MAX)return isP[x];for (int p : primes) {if (pow2(p) > x)return true;if (x % p == 0)return false;}for (int p = primes.back() + 1; pow2(p) <= x; p++)if (x % p == 0)return false;return true;}std::vector<u32> prime_list() const { return primes; }PF prime_factor(u64 n) const {assert(n <= pow2(MAX));if constexpr (PRIME_FACTOR)if (n <= MAX)return prime_factor[n];PF ret;for (u64 p : primes) {if (p * p > n)break;if (n % p)continue;ret.emplace_back(p, 0);while (n % p == 0) {ret.back().second++;n /= p;}}if (n > 1)ret.emplace_back(n, 1);return ret;}};PrimeUtil<1000000, true, false> P;int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::signal(SIGABRT, signal_hander);INT(n);std::vector<mint> dp(1000001, 0);REP (n) {INT(x);std::vector<int> pr;for (const auto &[p, e] : P.prime_factors[x])pr.push_back(p);int m = pr.size();mint sum = 1;REP (S, 1, 1 << m) {int prod = 1;REP (i, m)if (in(S, i))prod *= pr[i];if (std::popcount(unsigned(S)) & 1)sum += dp[prod];elsesum -= dp[prod];}REP (S, 1 << m) {int prod = 1;REP (i, m)if (in(S, i))prod *= pr[i];dp[prod] += sum;}}for (int i = 1; i <= 10; i++)debug(i, dp[i]);print(dp[1]);}