题目链接:http://codeforces.com/problemset/problem/1151/C
有一个只存奇数的集合A = {1, 3, 5……2*n - 1,……},和只存偶数的集合B = {2, 4, 6……2*n,……},现在要生成一个序列,这个序列分成i次生成:第1次从A中取1个放入序列,第2次从B中取2个放入序列,第3次从A中取4个放入序列,……,第2*n - 1次从A中取22*n-2个放入序列,第2*n次从B中取22*n-1个放入序列……。取得顺序是从小到大取的。题目给定一个区间,就序列在该区间所有数的累加和。
只要实现一个求区间[1, i]的函数getSum(i),那么任意区间内的和都可以算出,比如区间[l, r]的和为getSum(r) - getSum(l - 1)。
设odd_len为区间[1, i]上奇数的个数,even_len为区间[1, i]上偶数的个数。
只要求出了odd_len和even_len就可以用快速幂求出和了。
1 #pragma GCC optimize("Ofast") 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 #define INIT() std::ios::sync_with_stdio(false);std::cin.tie(0); 6 #define Rep(i,n) for (int i = 0; i < (n); ++i) 7 #define For(i,s,t) for (int i = (s); i <= (t); ++i) 8 #define rFor(i,t,s) for (int i = (t); i >= (s); --i) 9 #define ForLL(i, s, t) for (LL i = LL(s); i <= LL(t); ++i) 10 #define rForLL(i, t, s) for (LL i = LL(t); i >= LL(s); --i) 11 #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i) 12 #define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i) 13 14 #define pr(x) cout << #x << " = " << x << " " 15 #define prln(x) cout << #x << " = " << x << endl 16 17 #define LOWBIT(x) ((x)&(-x)) 18 19 #define ALL(x) x.begin(),x.end() 20 #define INS(x) inserter(x,x.begin()) 21 22 #define ms0(a) memset(a,0,sizeof(a)) 23 #define msI(a) memset(a,inf,sizeof(a)) 24 #define msM(a) memset(a,-1,sizeof(a)) 25 26 #define MP make_pair 27 #define PB push_back 28 #define ft first 29 #define sd second 30 31 template<typename T1, typename T2> 32 istream &operator>>(istream &in, pair<T1, T2> &p) { 33 in >> p.first >> p.second; 34 return in; 35 } 36 37 template<typename T> 38 istream &operator>>(istream &in, vector<T> &v) { 39 for (auto &x: v) 40 in >> x; 41 return in; 42 } 43 44 template<typename T1, typename T2> 45 ostream &operator<<(ostream &out, const std::pair<T1, T2> &p) { 46 out << "[" << p.first << ", " << p.second << "]" << "\n"; 47 return out; 48 } 49 50 typedef long long LL; 51 typedef unsigned long long uLL; 52 typedef pair< double, double > PDD; 53 typedef pair< int, int > PII; 54 typedef set< int > SI; 55 typedef vector< int > VI; 56 typedef map< int, int > MII; 57 const double EPS = 1e-10; 58 const int inf = 1e9 + 9; 59 const LL mod = 1e9 + 7; 60 const int maxN = 2e5 + 7; 61 const LL ONE = 1; 62 const LL evenBits = 0xaaaaaaaaaaaaaaaa; 63 const LL oddBits = 0x5555555555555555; 64 65 LL l, r; 66 LL ans; 67 // step[i] = 2^i 68 LL step[65]; 69 70 // Calculate x^y % mod 71 inline LL pow_mod(LL x, LL y, LL ans = 1){ 72 while(y){ 73 ans *= x; 74 ans %= mod; 75 --y; 76 } 77 return ans; 78 } 79 80 void STEP_INIT() { 81 step[0] = 1; 82 For(i, 1, 64) { 83 step[i] = pow_mod(2, 1, step[i - 1]); 84 } 85 } 86 87 // 二分计算x的二进制位数 88 inline int getBits(LL x) { 89 int cnt = 1; 90 while(x >>= 1) ++cnt; 91 return cnt; 92 } 93 94 // 计算1~x的和 95 LL getSum(LL x) { 96 LL ret = 0; 97 if(x == 0) return 0; 98 LL len = (LL)getBits(x); 99 LL odd_len = 0, even_len = 0; 100 if(len % 2 == 0) { // 落在偶数部分 101 even_len = (~(ONE << (len - ONE)) & x) + (((ONE << (len - ONE)) - ONE) & evenBits) + 1; 102 odd_len = x - even_len; 103 } 104 else { // 落在奇数部分 105 odd_len = (~(ONE << (len - ONE)) & x) + (((ONE << (len - ONE)) - ONE) & oddBits) + 1; 106 even_len = x - odd_len; 107 } 108 odd_len %= mod; 109 even_len %= mod; 110 111 // 快速幂 112 int i = odd_len, j = 29; 113 while(i > 0) { 114 while(i < step[j]) --j; 115 ret += (odd_len * step[j]) % mod; 116 ret %= mod; 117 i -= step[j]; 118 } 119 120 i = even_len + 1; 121 j = 29; 122 while(i > 0) { 123 while(i < step[j]) --j; 124 ret += (even_len * step[j]) % mod; 125 ret %= mod; 126 i -= step[j]; 127 } 128 return ret % mod; 129 } 130 131 int main(){ 132 INIT(); 133 cin >> l >> r; 134 135 STEP_INIT(); 136 137 ans = getSum(r) - getSum(l - 1); 138 ans += mod; 139 ans %= mod; 140 141 cout << ans << endl; 142 return 0; 143 } 144 /* 145 1 88005553534 146 203795384 147 148 1 99999999999 149 964936500 150 151 1 35 152 651 153 154 1 32 155 573 156 157 1 22 158 254 159 160 */
CodeForces 1151B Problem for Nazar
原文:https://www.cnblogs.com/zaq19970105/p/10750208.html