結果
問題 | No.1968 Distance |
ユーザー |
|
提出日時 | 2022-06-01 00:14:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,982 bytes |
コンパイル時間 | 5,141 ms |
コンパイル使用メモリ | 196,224 KB |
最終ジャッジ日時 | 2025-01-29 17:19:16 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#include<bits/stdc++.h>using namespace std;using i64=int64_t;using u64=uint64_t;template<u64 mod> struct Modint{u64 val;Modint(i64 val_=0):val((val_%i64(mod)+i64(mod))%i64(mod)){}Modint operator-(){return (val==0)?0:mod-val;}Modint operator+(Modint rhs){return Modint(*this)+=rhs;}Modint operator-(Modint rhs){return Modint(*this)-=rhs;}Modint operator*(Modint rhs){return Modint(*this)*=rhs;}Modint operator/(Modint rhs){return Modint(*this)/=rhs;}Modint pow(i64 rhs){Modint res=1,now=(*this);while(rhs){res*=((rhs&1)?now:1),now*=now,rhs>>=1;}return res;}Modint &operator+=(Modint rhs){val+=rhs.val,val-=((val>=mod)?mod:0);return (*this);}Modint &operator-=(Modint rhs){val+=((val<rhs.val)?mod:0),val-=rhs.val;return (*this);}Modint &operator*=(Modint rhs){val=val*rhs.val%mod;return (*this);}Modint &operator/=(Modint rhs){return (*this)*=rhs.pow(mod-2);}bool operator==(Modint rhs){return val==rhs.val;}bool operator!=(Modint rhs){return val!=rhs.val;}friend std::ostream &operator<<(std::ostream& os,Modint x){return os<<(x.val);}friend std::istream &operator>>(std::istream& is,Modint& x){u64 t;is>>t,x=t;return is;}};int main(){constexpr u64 mod=998244353;using mint=Modint<mod>;i64 N;cin>>N;mint ans=0;vector<mint> ln(61),dv(61);for(int i=0;i<=60;++i){ln[i]=mint(1)/((1ll<<i)+1);dv[i]=ln[i]*ln[i]/2;}for(int k=0;;++k){if(N<=(1ll<<k)-1){ans+=dv[k];break;}i64 l=0,r=k,p=1,q=1,now=N;while(0<now){if(l<=r){now-=q;q*=2;r--;}else{now-=p;p*=2;l--;}}if(l<=r){ans+=(dv[k]-dv[k+1])/(1ll<<(-l));}else{ans+=(ln[k]-ln[k+1]-(dv[k]-dv[k+1]))/(1ll<<(k-r));}}cout<<ans*2<<endl;}