题目链接：https://nanti.jisuanke.com/t/17118
题解：http://m.blog.csdn.net/kkkkahlua/article/details/78009087（很详细的大佬的博客）
画个图自己琢磨一下，考虑0----->n-1，对于到n-1的每个流，来自0--->i和i---->n-1这两部分，其实就是这两条边。考虑当前的这个i，化为二进制（和n等长），如果最高位是0，那么i与n-1异或的结果，最高位肯定是1。i与0异或最高位肯定是0,，那么，i--->n这条边的容量肯定是大于0--->i 的容量，所以0-->i-->n这个流的最大是0-->i的流，即最小割是0--->i这条边。如果最高位是1，那么0与i的异或值是大于i与n的异或值的，所以要割i--->n这条边。对于每个i从最低位向最高位找n-1中为1的位置，除了最高位，假设为1的这位是第 j 位，那么考虑n-1的最高位到j+1相同，而将第j为置为0，j---->0这些组合与原数异或，然后求和。
附代码：
#include <stdio.h> #include <algorithm> #include <math.h> #include <string.h> #include <vector> #include <queue> #include <map> #include <stack> #include <iostream> #define pi acos(-1.0) #define INF 0x3f3f3f3f using namespace std; #define ll long long const ll mod=1000000007; ll n; ll work() { if(n==2) return 1; n--; ll nn=n;ll ans=0; int len=0; while(nn) len++,nn>>=1; ans=((1ll<<(len-1))%mod-1+mod)%mod*((1ll<<(len-2))%mod)%mod;// cout<<ans<<endl; //计算1---->i中为最高位为0的前几位的流 ans=(ans+n)%mod; //计算0--->n-1的这条边的流 for(ll i=0;i<len-1;i++) //计算i的最高位为1的流 { if(n&(1ll<<i)) { if(i==0) ans=(ans+1)%mod; else ans=(ans+((((3ll<<i)%mod-1+mod)%mod)*((1ll<<(i-1))%mod))%mod)%mod;//,cout<<(3ll<<i)-1<<" "<<(1ll<<i)-1<<endl; } } return ans; } int main() { //freopen("C:\Users\Administrator\Desktop\a.txt","r",stdin); //ios::sync_with_stdio(false); //freopen("C:\Users\Administrator\Desktop\b.txt","w",stdout); while(scanf("%lld",&n)!=EOF) { ll tmp=work(); printf("%lld ",tmp); } return 0; }