結果

問題 No.3364 Push_back Operation
コンテスト
ユーザー Fu
提出日時 2025-11-17 22:47:23
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 173 ms / 2,000 ms
コード長 2,220 bytes
コンパイル時間 4,360 ms
コンパイル使用メモリ 234,312 KB
実行使用メモリ 7,840 KB
最終ジャッジ日時 2025-11-17 22:47:33
合計ジャッジ時間 9,479 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 53
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
typedef modint998244353 mint;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = 1; i <= (int)(n); i++)
#define ll long long
istream& operator>>(istream& is,mint& m) {
  long long val;
  is>>val;
  m=val;
  return is;
}
vector<mint> PTS(vector<mint> P,mint c){
  int n=P.size()-1;
  vector<mint> fact(n+1);
  vector<mint> invfact(n+1);
  vector<mint> cc(n+1);
  fact[0]=1;
  invfact[0]=1;
  cc[0]=1;
  rrep(i,n){
    fact[i]=fact[i-1]*i;
    cc[i]=cc[i-1]*c;
  }
  invfact[n]=fact[n].inv();
  for(int i=n-1;i>=1;i--) invfact[i]=invfact[i+1]*(i+1);
  vector<mint> X1(n+1);
  vector<mint> X2(n+1);
  rep(i,n+1){
    X1[i]=P[n-i]*fact[n-i];
    X2[i]=cc[i]*invfact[i];
  }
  vector<mint> X=convolution(X1,X2);
  vector<mint> ans(n+1);
  rep(i,n+1){
    ans[i]=X[n-i]*invfact[i];
  }
  return ans;
}
vector<mint> inv(const vector<mint>& f, int n) {
    assert(n > 0);
    assert(f.size() > 0 && f[0].val() != 0);
    vector<mint> H(1);
    H[0] = f[0].inv();
    
    int k = 1;
    while (k < n) {
        int k2 = k * 2;
        vector<mint> f_k(f.begin(), f.begin() + min((int)f.size(), k2));
        if (f_k.size() < k2) f_k.resize(k2, 0);
        vector<mint> H_k = H;
        H_k.resize(k2, 0);
        vector<mint> fH = convolution(f_k, H_k);
        vector<mint> T(k2);
        for(int i = 0; i < k2; i++) {
            T[i] = -fH[i];
        }
        T[0] += 2;
        H.resize(k2, 0);
        H = convolution(H, T);
        H.resize(k2);
        k = k2;
    }
    H.resize(n);
    return H;
}
int C=400009;
vector<mint> fact(C+1),invfact(C+1);
mint binom(int n,int r){
  if (r>n) return 0;
  else{
    return fact[n]*invfact[r]*invfact[n-r];
  }
}
int main(){
  fact[0]=1;
  invfact[0]=1;
  rrep(i,C) fact[i]=fact[i-1]*i;
  invfact[C]=fact[C].inv();
  for(int i=C-1;i>=1;i--) invfact[i]=invfact[i+1]*(i+1);
  ll n;
  cin>>n;
  mint ans=0;
  for(ll l=1;l<=n;){
    ll i=n/l;
    if(i==0) break;
    ll r=n/i;
    mint j=mint(i);
    mint s=0;
    if(j.val()==1) s=r-l+1;
    else{
      s=j.pow(l)*(j.pow(r-l+1)-1)*(j-1).inv();
    }
    ans+=s;
    l=r+1;
  }
  cout<<ans.val()<<endl;
}
0