結果

問題 No.2952 Invision of Multiples
ユーザー nouka28
提出日時 2024-09-12 21:57:49
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,279 bytes
コンパイル時間 5,378 ms
コンパイル使用メモリ 311,592 KB
実行使用メモリ 11,296 KB
最終ジャッジ日時 2024-09-13 16:12:56
合計ジャッジ時間 15,754 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8 TLE * 1 -- * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
using namespace std;
#include<atcoder/all>
using namespace atcoder;
using mint=atcoder::modint998244353;
const int B=0;
const int M=50000;
mint sum[B+1],sum2[B+1];
// n>d_i
mint floor_sums[M+1][B+1];
// d_i>n
mint floor_sums2[M+1][B+1];
//invs
mint invs[B+1];
int main(){
    cin.tie(nullptr),ios_base::sync_with_stdio(false);
    int n,m;cin>>n>>m;
    vector<int> a(n);for(auto&e:a)cin>>e;
    vector<mint> xa;
    mint X=1;
    for(auto&e:a){
        xa.push_back(m/e);
        X*=xa.back();
        xa.back()=xa.back().inv();
    }
    
    for(int i=1;i<=M;i++){
        for(int j=1;j<=B;j++){
            floor_sums[i][j]=floor_sum(m/j,i,j,j-1);
            floor_sums2[i][j]=floor_sum(m/i,j,i,i-1);
        }
    }
    for(int i=1;i<=B;i++){
        if(m/i==0)continue;
        invs[i]=mint(m/i).inv();
    }
    mint ans=0;
    fenwick_tree<mint> f(M+1);
    for(int i=0;i<n;i++){
        if(a[i]<=B){
            ans+=sum2[a[i]];
            for(int j=1;j<=B;j++){
                ans+=sum[j]*floor_sums[a[i]][j]*xa[i];
            }
            sum[a[i]]+=X*xa[i];
        }else{
            for(int j=1;j<=B;j++){
                ans+=sum[j]*floor_sums[a[i]][j]*xa[i];
            }
            for(int j=a[i];j<=m;j+=a[i]){
                ans+=f.sum(j+1,m+1)*xa[i];
            }
            for(int j=1;j<=B;j++){
                sum2[j]+=X*xa[i]*invs[j]*floor_sums2[a[i]][j];
            }
            for(int j=a[i];j<=M;j+=a[i]){
                f.add(j,X*xa[i]);
            }
        }
    }
    cout<<ans.val()<<endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0