結果

問題 No.737 PopCount
ユーザー jelljell
提出日時 2018-09-28 23:29:24
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 3,097 bytes
コンパイル時間 1,395 ms
コンパイル使用メモリ 164,860 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-12 07:22:45
合計ジャッジ時間 2,111 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 1 ms
6,816 KB
testcase_04 AC 2 ms
6,820 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 2 ms
6,816 KB
testcase_11 AC 2 ms
6,816 KB
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 2 ms
6,816 KB
testcase_16 AC 1 ms
6,816 KB
testcase_17 AC 2 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
// #include <boost/functional/hash.hpp>
// #include <boost/multiprecision/cpp_int.hpp>

#define debug 0
#define esc(ret) cout << (ret) << endl,quick_exit(0)
#define fcout(d) cout << fixed << setprecision(d)
#define urep(i,s,t) for(int i = (int)(s); i <= (int)(t); ++i)
#define drep(i,s,t) for(int i = (int)(s); i >= (int)(t); --i)
#define rep(i,n) urep(i,0,(n) - 1)
#define rep1(i,n) urep(i,1,(n))
#define all(v) begin(v),end(v)
#define rall(v) rbegin(v),rend(v)
#define vct vector
#define prique priority_queue
#define l_bnd lower_bound
#define u_bnd upper_bound
#define rsz resize
#define era erase
#define emp emplace
#define emf emplace_front
#define emb emplace_back
#define pof pop_front
#define pob pop_back
#define mkp make_pair
#define mkt make_tuple
#define fir first
#define sec second
#define odd(x) ((x) & 1)
#define even(x) (!odd(x))

using namespace std;

//typedef boost::multiprecision::cpp_int mlint;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef vct<vct<ll>> mat;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tiii;
typedef map<int,int> mpii;
typedef unordered_map<int,int> umpii;

const int dir[8][2] = { {1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,1},{-1,-1},{1,-1} };
const ll inf32 = (1 << 30) - 1;
const ll inf64 = (1LL << 62) - 1;
const ll mod = 1e9 + 7;
const db eps = 1e-9;

template <class T, class U> T qceil(T x, U y) { return x > 0 ? (x - 1) / y + 1 : x / y; }
template <class T, class U> bool parity(T x, U y) { return odd(x) ^ even(y); }
template <class T, class U> bool chmax(T &m, U x) { if(m < x) { m = x; return 1; } return 0; }
template <class T, class U> bool chmin(T &m, U x) { if(m > x) { m = x; return 1; } return 0; }
template <class T> bool cmprs(T &v) {
    T tmp = v;
    sort(all(tmp));
    tmp.erase(unique(all(tmp)),end(tmp));
    for(auto it = begin(v); it != end(v); ++it) *it = l_bnd(all(tmp),*it) - begin(tmp) + 1;
    return v.size() > tmp.size();
}
mat mulmat(mat &x, mat &y, ll md = mod) {
    int xrow = x.size();
    int xcol = x[0].size();
    int ycol = y[0].size();
    mat ret(xrow,vct<ll>(ycol));
    rep(i,xrow)rep(j,ycol)rep(k,xcol) ret[i][j] += x[i][k] * y[k][j] % md,ret[i][j] %= md;
    return ret;
}

template<class T> T gcd(T a, T b){ if(a % b) return gcd(b, a % b); return b; }

ll modpow(ll n, ll e, ll md = mod) {
    n %= md;
    if(!n) return 0;
    e %= md - 1;
    ll ret = 1;
    while(e) {
        if(e & 1) ret = ret * n % md;
        n = n * n % md;
        e /= 2;
    }
    return ret;
}

ll N;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin>>N;
    int d=0;
    ll ans=0,pw=1;
    while(pw <= N){
        pw*=2;
        ll tmp=0;
        ll q = N/pw;
        ll r = N%pw;
        tmp+=modpow(2,d)*((modpow(2,d)*3-1)%mod)%mod*((mod+1)/2)%mod*q%mod;
        tmp+=modpow(2,d*2)%mod*q%mod*(q-1)%mod;
        tmp%=mod;
        ll M=N-r+pw/2;
        if(N>=M)tmp+=(M%mod+N%mod)%mod*((N-M+1)%mod)%mod*((mod+1)/2)%mod;
        tmp%=mod;
        //cout<<tmp<<endl;
        ans=(ans+tmp)%mod;
        d++;
    }
    esc((ans+mod)%mod);
}
0