欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2017 ACM-ICPC 亚洲区(西安赛区)网络赛 E. Maximum Flow(最大流/规律)

程序员文章站 2022-06-30 22:49:18
...

题目:https://nanti.jisuanke.com/t/17118
题意:0~n-1个点,任意两点i,j,流量为i xor j,求0~n-1的最大流
思路:规律
首先打表
2017 ACM-ICPC 亚洲区(西安赛区)网络赛 E. Maximum Flow(最大流/规律)
以下参考http://blog.csdn.net/ShiWaiGaoRen12345/article/details/78007721

题解:
打印出来相邻两个数的差是有规律的, 差值的规律如下:
2^0+1 第一次出现的位置为2^1, 第二次出现的位置为2^1+2^0, 接下来出现的位置依次为:2^1+2^0+k*2^1;
2^2+1 第一次出现的位置为2^2, 第二次出现的位置为2^2+2^1, 接下来出现的位置依次为:2^2+2^1+k*2^2;
2^4+1 第一次出现的位置为2^3, 第二次出现的位置为2^3+2^2, 接下来出现的位置依次为:2^3+2^2+k*2^3;
2^6+1 第一次出现的位置为2^4, 第二次出现的位置为2^4+2^3, 接下来出现的位置依次为:2^4+2^3+k*2^4;
依次类推…..

代码:

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MOD = 1000000007;

ll p[205] = {1};
int main()
{
    for(int i = 1;i <= 62*2;i++)
        p[i] = p[i-1]*2%MOD;
    ll n;
    while(~scanf("%lld",&n))
    {
        ll ans = 1,sum = 1;
        for(int i = 1;i <= 62;i++)
        {
            sum <<= 1;
            if(sum >= n)
                break;
            ll tmp = p[(i-1)*2] + 1;//差值
            ans = (ans + tmp) % MOD;
            if(sum + sum/2 < n)
                ans = (ans + tmp) % MOD;
            else
                continue;
            if(sum + sum/2 < n)
                ans = (ans + tmp*(((n-1-(sum+sum/2))/sum)%MOD)) % MOD;
        }
        printf("%lld\n",ans);
    }
}
相关标签: 最大流 规律