题目地址：HDU 5269 比赛的时候想到了分治的思路，但是脑残了。，。写麻烦了。。。调了好久也没调出来。。(分治写的太少..)赛后优化了一下。。就过了。。 我的思路是先排序，排序是按照的将每个数字的二进制表示倒过来的字典序从大到小排，比如样例2中的2,6,5,4,0，二进制分别是010,110,101,100,000，排序之后是 101 110 010 100 000 这样的话就把后缀相同的都给放在一块了。其实也相当于字典树，不过比赛的时候没想到字典树，只想到了分治。。 然后从末位开始找，对所有该位为1的进行分治，再对所有该位为0的进行分治，，然后加上该位的0和1之间互相匹配导致的lowbit累加上。最后结果乘以2就可以了。 代码如下：
;mod=998244353;const int INF=0x3f3f3f3f;const double eqs=1e-9;const int MAXN=300000+10;int a[60000];LL ans;bool cmp(int x, int y){int i;for(i=0;i<30;i++){if((x&(1<<i))&&!(y&(1<<i))) return true;if(!(x&(1<<i))&&(y&(1<<i))) return false;}return true;}void dfs(int l, int r, int k){int i, pos=l-1;if(l>=r||k>=30) return ;for(i=l;i<=r;i++){if(a[i]&(1<<k))pos=i;else break;}ans+=(LL)(pos-l+1)*(r-pos)*(1<<k)%mod;dfs(l,pos,k+1);dfs(pos+1,r,k+1);}int main(){int t, n, i, icase=0, l, r, pos;scanf(“%d”,&t);while(t–){scanf(“%d”,&n);for(i=0;i<n;i++){scanf(“%d”,&a[i]);}sort(a,a+n,cmp);pos=-1;for(i=0;i<n;i++){if(a[i]&1)pos=i;else break;}ans=(LL)(pos+1)*(n-pos-1)%mod;dfs(0,pos,1);dfs(pos+1,n-1,1);printf(“Case #%d: %I64d\n”,++icase,(ans*2)%mod);}return 0;}
赚钱之道很多，但是找不到赚钱的种子，便成不了事业家。
