結果
問題 | No.2952 Invision of Multiples |
ユーザー | apricity |
提出日時 | 2024-11-24 15:43:51 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,297 ms / 4,000 ms |
コード長 | 8,727 bytes |
コンパイル時間 | 1,634 ms |
コンパイル使用メモリ | 143,216 KB |
実行使用メモリ | 91,908 KB |
最終ジャッジ日時 | 2024-11-24 15:44:37 |
合計ジャッジ時間 | 45,604 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 10 ms
46,816 KB |
testcase_01 | AC | 10 ms
46,816 KB |
testcase_02 | AC | 1,086 ms
47,208 KB |
testcase_03 | AC | 28 ms
48,936 KB |
testcase_04 | AC | 28 ms
47,732 KB |
testcase_05 | AC | 28 ms
49,336 KB |
testcase_06 | AC | 27 ms
48,944 KB |
testcase_07 | AC | 28 ms
47,476 KB |
testcase_08 | AC | 29 ms
49,292 KB |
testcase_09 | AC | 719 ms
74,776 KB |
testcase_10 | AC | 689 ms
72,528 KB |
testcase_11 | AC | 1,097 ms
91,176 KB |
testcase_12 | AC | 1,087 ms
90,608 KB |
testcase_13 | AC | 654 ms
72,512 KB |
testcase_14 | AC | 1,168 ms
91,032 KB |
testcase_15 | AC | 1,297 ms
91,720 KB |
testcase_16 | AC | 1,265 ms
91,876 KB |
testcase_17 | AC | 1,258 ms
91,908 KB |
testcase_18 | AC | 1,259 ms
91,836 KB |
testcase_19 | AC | 1,157 ms
91,300 KB |
testcase_20 | AC | 1,160 ms
90,728 KB |
testcase_21 | AC | 1,180 ms
91,748 KB |
testcase_22 | AC | 1,193 ms
91,688 KB |
testcase_23 | AC | 1,196 ms
91,844 KB |
testcase_24 | AC | 1,190 ms
91,888 KB |
testcase_25 | AC | 1,180 ms
91,900 KB |
testcase_26 | AC | 1,198 ms
91,780 KB |
testcase_27 | AC | 1,274 ms
91,900 KB |
testcase_28 | AC | 1,263 ms
91,892 KB |
testcase_29 | AC | 1,268 ms
91,796 KB |
testcase_30 | AC | 1,269 ms
91,820 KB |
testcase_31 | AC | 1,265 ms
91,832 KB |
testcase_32 | AC | 1,279 ms
91,680 KB |
testcase_33 | AC | 1,145 ms
91,312 KB |
testcase_34 | AC | 1,134 ms
91,036 KB |
testcase_35 | AC | 1,121 ms
90,952 KB |
testcase_36 | AC | 1,188 ms
91,000 KB |
testcase_37 | AC | 1,192 ms
90,976 KB |
testcase_38 | AC | 1,166 ms
91,076 KB |
testcase_39 | AC | 1,139 ms
91,432 KB |
testcase_40 | AC | 1,112 ms
91,188 KB |
testcase_41 | AC | 1,157 ms
91,188 KB |
testcase_42 | AC | 1,146 ms
91,060 KB |
testcase_43 | AC | 1,137 ms
91,472 KB |
ソースコード
#include<iostream> #include<string> #include<vector> #include<algorithm> #include<numeric> #include<cmath> #include<utility> #include<tuple> #include<cstdint> #include<cstdio> #include<iomanip> #include<map> #include<queue> #include<set> #include<stack> #include<deque> #include<unordered_map> #include<unordered_set> #include<bitset> #include<cctype> #include<chrono> #include<random> #include<cassert> #include<cstddef> #include<iterator> #include<string_view> #include<type_traits> #ifdef LOCAL # include "debug_print.hpp" # define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__) #else # define debug(...) (static_cast<void>(0)) #endif using namespace std; #define rep1(a) for(int i = 0; i < a; i++) #define rep2(i, a) for(int i = 0; i < a; i++) #define rep3(i, a, b) for(int i = a; i < b; i++) #define rep4(i, a, b, c) for(int i = a; i < b; i += c) #define overload4(a, b, c, d, e, ...) e #define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__) #define rrep1(a) for(int i = (a)-1; i >= 0; i--) #define rrep2(i, a) for(int i = (a)-1; i >= 0; i--) #define rrep3(i, a, b) for(int i = (b)-1; i >= a; i--) #define rrep4(i, a, b, c) for(int i = (b)-1; i >= a; i -= c) #define rrep(...) overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__) #define ALL(v) v.begin(), v.end() #define RALL(v) v.rbegin(), v.rend() #define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() ); #define pb push_back using ll = long long; using D = double; using LD = long double; using P = pair<int, int>; using vi = vector<int>; using vl = vector<ll>; template <class T> using vc = vector<T>; template <class T> using vvc = vector<vc<T>>; template <class T> using vvvc = vector<vvc<T>>; template <class T> using vvvvc = vector<vvvc<T>>; template <class T> using vvvvvc = vector<vvvvc<T>>; #define vv(type, name, h, ...) \ vector<vector<type>> name(h, vector<type>(__VA_ARGS__)) #define vvv(type, name, h, w, ...) \ vector<vector<vector<type>>> name( \ h, vector<vector<type>>(w, vector<type>(__VA_ARGS__))) #define vvvv(type, name, a, b, c, ...) \ vector<vector<vector<vector<type>>>> name( \ a, vector<vector<vector<type>>>( \ b, vector<vector<type>>(c, vector<type>(__VA_ARGS__)))) template<typename T> using PQ = priority_queue<T,vector<T>>; template<typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>; template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; } void yesno(bool flag) {cout << (flag?"Yes":"No") << "\n";} template<typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) { os << p.first << " " << p.second; return os; } template<typename T, typename U> istream &operator>>(istream &is, pair<T, U> &p) { is >> p.first >> p.second; return is; } template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { int s = (int)v.size(); for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i]; return os; } template<typename T> istream &operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; } void in() {} template<typename T, class... U> void in(T &t, U &...u) { cin >> t; in(u...); } void out() { cout << "\n"; } template<typename T, class... U, char sep = ' '> void out(const T &t, const U &...u) { cout << t; if (sizeof...(u)) cout << sep; out(u...); } void outr() {} template<typename T, class... U, char sep = ' '> void outr(const T &t, const U &...u) { cout << t; outr(u...); } template <uint32_t mod> struct LazyMontgomeryModInt { using mint = LazyMontgomeryModInt; using i32 = int32_t; using u32 = uint32_t; using u64 = uint64_t; static constexpr u32 get_r() { u32 ret = mod; for (i32 i = 0; i < 4; ++i) ret *= 2 - mod * ret; return ret; } static constexpr u32 r = get_r(); static constexpr u32 n2 = -u64(mod) % mod; static_assert(mod < (1 << 30), "invalid, mod >= 2 ^ 30"); static_assert((mod & 1) == 1, "invalid, mod % 2 == 0"); static_assert(r * mod == 1, "this code has bugs."); u32 a; constexpr LazyMontgomeryModInt() : a(0) {} constexpr LazyMontgomeryModInt(const int64_t &b) : a(reduce(u64(b % mod + mod) * n2)){}; static constexpr u32 reduce(const u64 &b) { return (b + u64(u32(b) * u32(-r)) * mod) >> 32; } constexpr mint &operator+=(const mint &b) { if (i32(a += b.a - 2 * mod) < 0) a += 2 * mod; return *this; } constexpr mint &operator-=(const mint &b) { if (i32(a -= b.a) < 0) a += 2 * mod; return *this; } constexpr mint &operator*=(const mint &b) { a = reduce(u64(a) * b.a); return *this; } constexpr mint &operator/=(const mint &b) { *this *= b.inverse(); return *this; } constexpr mint operator+(const mint &b) const { return mint(*this) += b; } constexpr mint operator-(const mint &b) const { return mint(*this) -= b; } constexpr mint operator*(const mint &b) const { return mint(*this) *= b; } constexpr mint operator/(const mint &b) const { return mint(*this) /= b; } constexpr bool operator==(const mint &b) const { return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a); } constexpr bool operator!=(const mint &b) const { return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a); } constexpr mint operator-() const { return mint() - mint(*this); } constexpr mint operator+() const { return mint(*this); } constexpr mint pow(u64 n) const { mint ret(1), mul(*this); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } constexpr mint inverse() const { int x = get(), y = mod, u = 1, v = 0, t = 0, tmp = 0; while (y > 0) { t = x / y; x -= t * y, u -= t * v; tmp = x, x = y, y = tmp; tmp = u, u = v, v = tmp; } return mint{u}; } friend ostream &operator<<(ostream &os, const mint &b) { return os << b.get(); } friend istream &operator>>(istream &is, mint &b) { int64_t t; is >> t; b = LazyMontgomeryModInt<mod>(t); return (is); } constexpr u32 get() const { u32 ret = reduce(a); return ret >= mod ? ret - mod : ret; } static constexpr u32 get_mod() { return mod; } }; const int mod = 998244353; //const int mod = 1000000007; using mint = LazyMontgomeryModInt<mod>; /* * dual segtree * range apply / point get * operator (com) must be commutative: * f g = g f * ex) range add, chmax/chmin, (apply) * https://hackmd.io/@tatyam-prime/DualSegmentTree */ template< class T, T (*id)(), void(*com)(T&, const T&) > struct DualSegmentTree { int sz; vector< T > dat; DualSegmentTree(int n){ sz = 1; while(sz < n) sz <<= 1; dat.assign(2*sz, id()); } void apply(int l, int r, const T &t){ l += sz; r += sz; for(;l<r;l>>=1,r>>=1){ if(l&1) com(dat[l++], t); if(r&1) com(dat[--r], t); } } T get(int i) const{ T res = id(); i += sz; for(;i;i>>=1){ com(res, dat[i]); } return res; } }; using T = mint; T id() {return 0;} void com(T &a, const T &b) {a += b;} #include "atcoder/math.hpp" constexpr int MX = 50005; constexpr int B = 224; int f1[B][MX]; // f1[x][y] = #(i<j) di=x, dj=y int f2[MX][B]; DualSegmentTree<T,id, com> g(MX); int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n,m; in(n,m); vector<int> d(n); in(d); vector<mint> im(m+1); rep(i,1,m+1) im[i] = mint(m/i).inverse(); vector<int> cntd(m+1); rep(i,n) { rep(j,B) f1[j][d[i]] += cntd[j]; cntd[d[i]]++; } cntd.assign(m+1,0); rrep(i,n){ rep(j,B) f2[d[i]][j] += cntd[j]; cntd[d[i]]++; } mint ans = 0; rep(x,1,B) rep(y,1,m+1) { ans += im[x] * im[y] * f1[x][y] * atcoder::floor_sum(m/x, y, x, x-1); } rep(x,B,m+1) rep(y,1,B) { ans += im[x] * im[y] * f2[x][y] * atcoder::floor_sum(m/x, y, x, x-1); } rrep(i,n) if(d[i] >= B) { mint tmp = 0; rep(l,1,m/d[i]+1) tmp += g.get(l*d[i]-1); ans += tmp * im[d[i]]; rep(t,1,m/d[i]+1) { int l = t*d[i], r = min(m,(t+1)*d[i]-1) + 1; g.apply(l,r,im[d[i]]*t); } } rep(i,n) ans *= m/d[i]; out(ans); }