#289320 (C++11（廃止可能性あり）) No.737 PopCount

• 問題: No.737 PopCount
• ユーザー: jell
• 提出日時: 2018-10-03 23:15:54
• 言語: C++11（廃止可能性あり） (gcc 13.3.0)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 4,496 bytes
• コンパイル時間: 1,725 ms
• コンパイル使用メモリ: 162,600 KB
• 最終ジャッジ日時: 2024-11-14 20:38:42
• 合計ジャッジ時間: 2,525 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

コンパイルメッセージ

main.cpp:119:5: error: ‘prm_tbl’ function uses ‘auto’ type specifier without trailing return type
  119 |     auto prm_tbl(int n) {
      |     ^~~~
main.cpp:119:5: note: deduced return type only available with ‘-std=c++14’ or ‘-std=gnu++14’
main.cpp:132:5: error: ‘prm_fac’ function uses ‘auto’ type specifier without trailing return type
  132 |     auto prm_fac(ll n) {
      |     ^~~~
main.cpp:132:5: note: deduced return type only available with ‘-std=c++14’ or ‘-std=gnu++14’

ソースコード

#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 rrep(i,n) drep(i,(n) - 1,0)
#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) (~(x) & 1)

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();
}

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

template<class T> T lcm(T a, T b){ if(a | b) return a / gcd(a, b) * b; return max(abs(a),abs(b)); }


struct Mathfn {
    ll md;
    vct<ll> fact_tbl,invfact_tbl;

    Mathfn(int n = 1e6, ll m = mod) {
        md = m;
        fact_init(n);
        invfact_init(n);
    }

    void fact_init(int n) {
        fact_tbl.resize(n + 1);
        fact_tbl[0] = 1;
        for(int i = 1; i <= n; i++) fact_tbl[i] = fact_tbl[i - 1] * i % md;
    }

    ll fact(int x) {
        return x >= 0 ? fact_tbl[x] : 0;
    }

    void invfact_init(int n) {
        invfact_tbl.resize(n + 1);
        invfact_tbl[n] = modinv(fact(n));
        for(int i = n; i > 0; i--) invfact_tbl[i - 1] = invfact_tbl[i] * i % md;
    }

    ll invfact(int x) {
        return x >= 0 ? invfact_tbl[x] : 0;
    }

    ll comb(int x, int y) {
        return fact(x) * invfact(y) % md * invfact(x - y) % md;
    }

    ll modpow(ll n, ull e) {
        if(!e) return 1;
        if(!(n %= mod)) return 0;
        return modpow(n * n % md,e / 2) * (e & 1 ? n : 1) % md;
    }

    ll modinv(ll n) {
        return modpow(n,md - 2);
    }

    bool prm_jdg(ll n){
    	if(n == 2) return 1;
    	if(n <= 1 || ~n & 1) return 0;
    	for(ll d = 3; d * d <= n; d += 2) if(!(n % d)) return 0;
    	return 1;
    }

    auto prm_tbl(int n) {
        vct<bool> ret(n + 1,1);
      	urep(i,2,n / 2) ret[i * 2] = 0;
      	ret[0] = ret[1] = 0;
      	int p = 3;
      	while(p * p <= n) {
      		for(int t = p * 3; t <= n; t += p * 2) ret[t] = 0;
      		p += 2;
      		while(!ret[p]) p += 2;
      	}
      	return ret;
    }

    auto prm_fac(ll n) {
        unordered_map<int,int> ret;
        int cnt = 0;
        for(ll d = 2; d * d <= n; d++) {
            while(n % d == 0) {
                cnt++;
                n /= d;
            }
            if(cnt) {
               ret[d] = cnt;
               cnt = 0;
            }
        }
        if(n > 1) ret[n] = 1;
        return ret;
    }
};

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

    Mathfn mf;
    ll n,ans=0;
    cin >> n;
    n++;
    for(ll pw = 2; pw/2 < n; pw*=2){
        ll m = n - (n % pw);
        ll k = min(m + pw/2,n);
        ll l = (n - k) % mod;
        ll r = (n + k - 1) % mod;
        m %= mod;
        ans += m * ((m + pw/2 - 1) % mod) % mod * mf.modinv(4) % mod + l * r % mod * mf.modinv(2) % mod;
        ans = (ans + mod) % mod;
    }
    esc(ans);
}