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的最大流
思路:规律
首先打表
以下参考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);
}
}
上一篇: 站长百科访谈:谈谈网站运营那些事
下一篇: 站长百科访谈:毛红亮讲述互联网经历