QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#844908#3472. EvenOddASnownAC ✓1ms3828kbC++174.5kb2025-01-06 12:18:032025-01-06 12:18:07

Judging History

This is the latest submission verdict.

  • [2025-01-06 12:18:07]
  • Judged
  • Verdict: AC
  • Time: 1ms
  • Memory: 3828kb
  • [2025-01-06 12:18:03]
  • Submitted

answer

#include<bits/stdc++.h>
#define file(F) freopen(#F".in","r",stdin),freopen(#F".out","w",stdout)
#define lowbit(x) ((x)&-(x))
#define ALL(x) (x).begin(),(x).end()
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define popc(x) (__builtin_popcountll((x)))
#define abs(x) ((x)>=0?(x):-(x))
using namespace std;
using ll=long long;
using uint=uint32_t;
namespace asnown {
using i32=int32_t; using u32=uint32_t;
using i64=int64_t; using u64=uint64_t;
using i128=__int128_t; using u128=__uint128_t; };
template<typename T>
inline bool Max(T &x,T y) { return std::less<T>()(x,y)&&(x=y,true); }
template<typename T>
inline bool Min(T &x,T y) { return std::less<T>()(y,x)&&(x=y,true); }
void Solve();
namespace asnown {
constexpr i32 inverse(i32 a,i32 m) { i64 r=1;
   for(;a>1;a=m%a) r=r*(m-m/a)%m; return r; }
template<i32 m>
class static_modint { 
   using mint=static_modint;
public:
   constexpr static_modint() : v(0) {}
   constexpr static_modint(i32 v) : v(normal(v%m)) {}
   constexpr static_modint(u32 v) : v(v%m) {}
   constexpr static_modint(i64 v) : v(normal(v%m)) {}
   constexpr static_modint(u64 v) : v(v%m) {}
   constexpr static_modint(ll v) : v(normal(v%m)) {}
   constexpr static_modint(i128 v) : v(normal(v%m)) {}
   constexpr static_modint(u128 v) : v(v%m) {}
   constexpr u32 normal(i32 v) { if(v>=m) v-=m; return v+((v>>31)&m); }
   constexpr u32 val() const { return v; }
   constexpr static u32 mod() { return m; }
   constexpr explicit operator bool() const { return v; }
   constexpr mint inv() const { assert(v!=0); return mint(inverse(v,m)); }
   constexpr mint pow(i64 b) const { assert(b>=0); 
      mint a=*this,res=1; for(;b;b>>=1,a*=a) if(b&1) res*=a; return res; }
   constexpr mint operator+() const { return *this; }
   constexpr mint operator-() const { return mint()-*this; }
   constexpr mint& operator+=(const mint &p) { return v=normal(v+p.v),*this; }
   constexpr mint& operator-=(const mint &p) { return v=normal(v-p.v),*this; }
   constexpr mint& operator++() { return (*this)+=1; }
   constexpr mint& operator--() { return (*this)-=1; }
   constexpr mint& operator++(i32) { auto tmp=*this; return ++*this,tmp; }
   constexpr mint& operator--(i32) { auto tmp=*this; return --*this,tmp; }
   constexpr mint& operator*=(const mint &p) { v=i64(v)*p.v%m; return *this; }
   constexpr mint& operator/=(const mint &p) { return *this *= p.inv(); }
   constexpr friend mint operator+(const mint &p,const mint &q) { return mint(p)+=q; }
   constexpr friend mint operator-(const mint &p,const mint &q) { return mint(p)-=q; }
   constexpr friend mint operator*(const mint &p,const mint &q) { return mint(p)*=q; }
   constexpr friend mint operator/(const mint &p,const mint &q) { return mint(p)/=q; }
   constexpr friend std::istream& operator>>(std::istream &is,mint &a) { i64 v; is>>v; a=v; return is; }
   constexpr friend std::ostream& operator<<(std::ostream &os,const mint &a) { os<<a.val(); return os; }
   constexpr bool operator==(const mint& p) const { return val()==p.val(); }
   constexpr bool operator!=(const mint& p) const { return val()!=p.val(); }
private:
   u32 v;
};
using modint998244353=static_modint<998244353>;
using modint107=static_modint<1000000007>;
};
using mint=asnown::modint107;
using asnown::i128;
const i128 one=1;
int ff(int x) {
   int step=0;
   while(x!=1) {
      if(x&1) x++; else x>>=1;
      ++step;
   } return step;
}
int fff(int x) {
   if(x==1) return 0;
   int bc=1<<__lg(x-1)+1;
   return __lg(bc)+popc(bc-x);
}
bool X[100];
pair<mint,mint> f[100];
pair<mint,mint> dp(int pos,bool lim) {
   if(pos==-1) return {1,0};
   if(!lim&&f[pos].first!=-1) return f[pos];
   mint cnt=0,ans=0;
   auto p=dp(pos-1,lim&(!X[pos]));
   cnt+=p.first,ans+=p.second;
   if(!lim||X[pos]) {
   auto p=dp(pos-1,lim);
   cnt+=p.first,ans+=p.first+p.second;
   }
   if(!lim) f[pos]={cnt,ans};
   return {cnt,ans};
}
mint spc(i128 R) {
   for(int l=0;l<62;l++) X[l]=R>>l&1;
   for(int l=0;l<62;l++) f[l]={-1,-1};
   return dp(61,true).second;
}
mint calc(i128 R) {
   if(R<=1) return 0;
   mint ans0=0,ans1;
   i128 i,o;
   for(i=1,o=2;o<=R;o+=one<<i++) {
      ans0+=i*mint(one<<i-1);
      ans1+=spc((one<<i-1)-1);
   }
   o-=one<<i-1;
   ans0+=i*(R-o);
   ans1+=spc((one<<i-1)-1)-spc((one<<i-1)-R+o-1);
   return ans0+ans1;
}
signed main() {
#ifndef ONLINE_JUDGE
#endif
   cin.tie(nullptr)->sync_with_stdio(false);
   Solve();
}
void Solve() {
   ll l,r; cin>>l>>r;
   cout<<calc(r)-calc(l-1)<<endl;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3520kb

input:

1 127

output:

1083

result:

ok single line: '1083'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

74 74

output:

11

result:

ok single line: '11'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3604kb

input:

188481480076382025 735477894373585094

output:

603589184

result:

ok single line: '603589184'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3828kb

input:

221018194823646727 598132723231895586

output:

593435414

result:

ok single line: '593435414'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3540kb

input:

723254527395008082 857000792713570284

output:

130769773

result:

ok single line: '130769773'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3600kb

input:

308610764995277671 886546357678103983

output:

981434297

result:

ok single line: '981434297'

Test #7:

score: 0
Accepted
time: 1ms
memory: 3652kb

input:

467129058436471616 929946560335162000

output:

956030241

result:

ok single line: '956030241'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3540kb

input:

142308250729181166 793647580012269898

output:

890073540

result:

ok single line: '890073540'

Test #9:

score: 0
Accepted
time: 1ms
memory: 3592kb

input:

30010612464177072 225060844674934062

output:

192815207

result:

ok single line: '192815207'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

1 1

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

1 1000000000000000000

output:

826523937

result:

ok single line: '826523937'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

1 999999999999999999

output:

826523858

result:

ok single line: '826523858'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3540kb

input:

4 16384

output:

311294

result:

ok single line: '311294'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3768kb

input:

4398046511104 18014398509481984

output:

451815097

result:

ok single line: '451815097'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3472kb

input:

4096 281474976710656

output:

231757660

result:

ok single line: '231757660'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

16 137438953472

output:

983959228

result:

ok single line: '983959228'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3508kb

input:

8192 16777216

output:

570281997

result:

ok single line: '570281997'