結果
問題 | No.2952 Invision of Multiples |
ユーザー | a1048576 |
提出日時 | 2024-10-25 22:24:01 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,815 bytes |
コンパイル時間 | 6,017 ms |
コンパイル使用メモリ | 327,468 KB |
実行使用メモリ | 24,064 KB |
最終ジャッジ日時 | 2024-10-25 22:26:14 |
合計ジャッジ時間 | 126,357 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 9 ms
8,960 KB |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | TLE | - |
testcase_16 | TLE | - |
testcase_17 | TLE | - |
testcase_18 | WA | - |
testcase_19 | TLE | - |
testcase_20 | TLE | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | TLE | - |
testcase_24 | AC | 3,841 ms
14,720 KB |
testcase_25 | AC | 3,918 ms
14,720 KB |
testcase_26 | TLE | - |
testcase_27 | TLE | - |
testcase_28 | TLE | - |
testcase_29 | TLE | - |
testcase_30 | TLE | - |
testcase_31 | TLE | - |
testcase_32 | TLE | - |
testcase_33 | WA | - |
testcase_34 | WA | - |
testcase_35 | WA | - |
testcase_36 | TLE | - |
testcase_37 | TLE | - |
testcase_38 | WA | - |
testcase_39 | WA | - |
testcase_40 | WA | - |
testcase_41 | WA | - |
testcase_42 | WA | - |
testcase_43 | WA | - |
ソースコード
#include<bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using mint = modint998244353; #define int long long int gcd_f(int x, int y) { if(x < y) swap(x,y); if(y == 0) return x; if(x%y == 0) return y; else return gcd_f(y,x%y); } struct Segtree { vector<vector<mint>> num; vector<int> p; int n; Segtree(int N) { n = N; num.resize(n); p.resize(n+1); p[0] = 1; for(int i = 0; i < n; i++) p[i+1] = p[i]*2; for(int i = 0; i < n; i++) num[i].assign(p[i],0); } void add(int x, mint y) { num[n-1][x] = num[n-1][x]+y; int t = x; for(int i = n-2; i >= 0; i--) { t/=2; num[i][t] = num[i+1][t*2]+num[i+1][t*2+1]; } } mint sum_calc(int t, int l, int r, int x, int y) { int m = (l+r)/2; if(t == n) return 0; if(x <= l && r <= y) return num[t][l/p[n-t-1]]; if(r <= x || y <= l) return 0; return sum_calc(t+1,l,m,x,y)+sum_calc(t+1,m,r,x,y); } mint sum(int l, int r) { return sum_calc(0,0,p[n-1],l,r); } }; int m; signed main() { int n; cin >> n >> m; vector<int> a(n); for(int i = 0; i < n; i++) cin >> a[i]; int e = 200; mint ans = 0; vector<mint> g(n+1,1),h(n,0), h2(n); for(int i = 0; i < n; i++) h[i] = m/a[i], g[i+1] = g[i]*h[i], h2[i] = mint(1)/h[i]; vector<vector<mint>> d(m+1); vector<vector<int>> c(m+1); for(int i = 0; i < n; i++) c[a[i]].push_back(i); for(int i = 0; i <= m; i++) { int l = c[i].size(); d[i].resize(l+1,0); for(int j = 0; j < l; j++) d[i][j+1] = d[i][j]+mint(1)*h2[c[i][j]]; } for(int i = 1; i <= n; i++) e = min(e,m); for(int i = 0; i < n; i++) { for(int j = 1; j <= e; j++) { int f = upper_bound(c[j].begin(),c[j].end(),i)-c[j].begin(); int z = m/a[i]; int L = c[j].size(); mint u = d[j][L]-d[j][f]; int x = a[i]*j/gcd_f(a[i],j); ans+=(floor_sum(z,j,a[i],a[i])-m/x)*g[n]*u*h2[i]; //cout << i << ' ' << j << ' ' << ans.val() << endl; } } for(int i = 0; i < n; i++) { if(a[i] <= e) continue; for(int j = 1; j <= e; j++) { int f = lower_bound(c[j].begin(),c[j].end(),i)-c[j].begin(); int z = m/j; int L = c[j].size(); mint u = d[j][f]; int x = (a[i]*j/gcd_f(a[i],j)); ans+=(floor_sum(z,j,a[i],a[i])-m/x)*g[n]*u*h2[i]; //cout << i << ' ' << j << ' ' << ans.val() << endl; } } vector<vector<int>> s(m+1); for(int i = 0; i < n; i++) { if(a[i] <= e) continue; for(int j = a[i]; j <= m; j+=a[i]) s[j].push_back(i); } Segtree seg(17); for(int i = e+1; i <= m; i++) { int l = s[i].size(); //cout << l << endl; for(int j = 0; j < l; j++) ans+=seg.sum(s[i][j]+1,n)*g[n]*h2[s[i][j]]; for(int j = 0; j < l; j++) seg.add(s[i][j],mint(1)*h2[s[i][j]]); } cout << ans.val() << endl; }