Maximum Flow 规律题 2017 ACM-ICPC 亚洲区（西安赛区）网络赛

Given a directed graph with $n$ nodes, labeled $0,1,\cdots ,n-1$.

For each $<i,j>$ satisfies $0\le i<j<n$, there exists an edge from the i-th node to the j-th node, the capacity of which is $i$ xor $j$.

Find the maximum flow network from the 0-th node to the (n-1)-th node, modulo $1000000007$.

Input Format

Multiple test cases (no more than $10000$).

In each test case, one integer in a line denotes n(2 \le n \le 10^{18})n(2≤n≤10​18​​).

Output Format

Output the maximum flow modulo $1000000007$for each test case.

样例输入

2

样例输出

1

完完全全找的规律,累死

先打了个表,发现其相邻数之差是有规律的

然后就各种调....

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;

ll n;
ll er[1000];
ll er1[66];
ll ant[1000];

int main()
{
    er[0] = 1;
    er1[0] =1  ;
    for(int i=1;i<=129;i++)
    {
        er[i] = 2*er[i-1]%MOD;
    }

    for(int i=1;i<=64;i++)
    {
        er1[i] = er1[i-1]*2;
    }

    ant[0] = 2;
    for(int i=1;i<=64;i++)
    {
        ant[i] = er[i*2]+1;
        ant[i]%=MOD;
    }

    ll tt = ant[0];
    ll pr;
    for(int i=1;i<=64;i++)
    {
        pr= ant[i];
        ant[i] = (ant[i]+MOD-tt)%MOD;
        tt = pr;
//        cout <<ant[i]<<endl;
    }
//    freopen("data.txt","r",stdin);
    while(cin >> n)
    {
        if(n==2)
        {
            cout<<1<<endl;
            continue;
        }
        ll ans = 0;
        ll t;
        for(int i=0;i<=64;i++)
        {
            if(n<er1[i])
                break;
            if(n%er1[i]==0)
            {
                t=  n/er1[i];
            }
            else
            {
                t=  n/er1[i]+1;
            }
            t-=2;
            if(t<=0)
            {
                break;
            }
//            cout <<t<<endl;
            t%=MOD;
            ans += t*ant[i];
            ans%=MOD;
        }
        cout << ans+1<<endl;
    }
    return 0;
}