codeforces 768B （推理+归纳）

题目原文：

Jon fought bravely to rescue the wildlings who were attacked by the white-walkers at Hardhome. On his arrival, Sam tells him that he wants to go to Oldtown to train at the Citadel to become a maester, so he can return and take the deceased Aemon's place as maester of Castle Black. Jon agrees to Sam's PRoposal and Sam sets off his journey to the Citadel. However becoming a trainee at the Citadel is not a cakewalk and hence the maesters at the Citadel gave Sam a problem to test his eligibility.

Initially Sam has a list with a single elementn. Then he has to perform certain Operations on this list. In each operation Sam must remove any element x, such thatx > 1, from the list and insert at the same position ,, sequentially. He must continue with these operations until all the elements in the list are either 0 or1.

Now the masters want the total number of1s in the rangel tor (1-indexed). Sam wants to become a maester but unfortunately he cannot solve this problem. Can you help Sam to pass the eligibility test?

The first line contains three integersn,l,r (0 ≤ n < 2⁵⁰,0 ≤ r - l ≤ 10⁵,r ≥ 1,l ≥ 1) – initial element and the range l tor.

It is guaranteed thatr is not greater than the length of the final list.

Output the total number of1s in the rangel tor in the final sequence.

解题思路：尝试将题目中所给的样例分析可以得到最终的序列里所有的奇数位都是1。因为所有的奇数位都可以看成是由第一位对称生成的，而根据题目中的定义可以知道第一位必然是1。然后考虑偶数位的情况。

              10            5 0 5      2 1 2 0 2 1 2 101110101011101

  2  5  2  10 2 5  2

将10分解可以得到1 2 5 10四个数。所有偶数位的数都跟他所对应上一层的数有关，经过观察分析可知，第二位的偶数对应第一个因子，第四位偶数对应第二个因子，第八位偶数对一个第三个因子，所以猜测和2的次幂有关。进一步验证可以知道对应第几个因子与其所在的偶数位可以分解成二的几次幂有关。

AC代码：

#include <bits/stdc++.h>#define Fori(x) for(int i=0;i<x;i++)#define Forj(x) for(int j=0;j<x;j++)#define maxn 2500#define inf 0x3f3f3f3f#define ONES(x) __builtin_popcount(x)using namespace std;typedef long long ll ;const double eps =1e-8;const int mod = 1000000007;typedef pair<int, int> P;const double PI = acos(-1.0);int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};int n,m;ll ans;vector<ll> a;vector<ll> b;int main(){    //freopen("test.txt","r",stdin);    ios_base::sync_with_stdio(false);    cin.tie(0);    ll n,l,r;    cin>>n>>l>>r;    if(n==0)    {        cout << 0 << endl;        return 0;    }    while(n)    {        //cout << n << endl;        a.push_back(n);        n /= 2;    }    reverse(a.begin(),a.end());    for(ll i = l; i<=r; i++ )    {        if(i%2)            ans++;        else        {            ll num = i;            int cnt = 0;            while(num%2==0)            {                num /= 2;                cnt++;            }            ans += a[cnt]%2;        }    }    cout << ans << endl;    return 0;}