結果

問題 No.737 PopCount
コンテスト
ユーザー どらら
提出日時 2018-09-29 01:05:19
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 1,583 bytes
コンパイル時間 1,609 ms
コンパイル使用メモリ 167,648 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-12 07:51:12
合計ジャッジ時間 2,253 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

const static ll MOD = 1000000007LL;

ll extgcd(ll a, ll b, ll &x, ll &y){
  ll d = a;
  if(b!=0){
    d = extgcd(b,a%b,y,x);
    y -= (a/b)*x;
  }else{
    x = 1; y = 0;
  }
  return d;
}

ll mod_inverse(ll a, ll m){
  ll x, y;
  extgcd(a, m, x, y);
  return (m+x%m)%m;
}

ll sum(ll a, ll d, ll n){
  a %= MOD;
  d %= MOD;
  n %= MOD;
  ll x = (n==0)?MOD-1:n-1;
  ll ret = n;
  ret *= ((2*a) % MOD + (x * d) % MOD) % MOD;
  ret %= MOD;
  ret *= mod_inverse(2, MOD);
  ret %= MOD;

  return ret;
}

ll calc(ll k, ll N){
  ll a = 1LL<<(k-1);
  ll p = 1LL<<k;

  if(N < a) return 0;

  ll m = (N-a) / p + 1;

  ll Sn1 = sum(0, p, m);
  Sn1 *= a % MOD;
  Sn1 %= MOD;
  ll Sn2 = sum(a, 1, a);
  Sn2 *= m % MOD;
  Sn2 %= MOD;

  //cout << a << " " << p << " " << m << " " << Sn1 << " " << Sn2 << endl;
  
  ll ret = (Sn1 + Sn2) % MOD;

  if(N < (a+a-1)+(m-1)*p){
    ll fst = N+1;
    ll lst = (a+a-1)+(m-1)*p;
    ll num = lst - (fst-1);
    ll Sn = sum(fst, 1, num);
    //cout << "\t" << fst << " " << lst << " " << num << " " << Sn << endl;
    ret += MOD - Sn;
    ret %= MOD;
  }
  //cout << k << "\t" << ret << endl;
  return ret;
}



int main(){
  ll N;
  cin >> N;

  ll ret = 0;
  rep(i,63){
    ret += calc(i+1, N);
    ret %= MOD;
  }

  cout << ret << endl;
  
  return 0;
}
0