文章目錄

• 題目描述
• 解析
• 代碼

題目描述

解析

做了巨長時間…
進行了一次刺激的閱讀理解競賽…
感謝whh dalao！
那么讓我們分析一下這道題
首先我們考慮單個求x選手的q值
不難發現
i 在第j天和x的大小關系只與a[x]與a[i]二進制下不同的最高位k有關
j的第k位與x相同時，a[i]就大，否則反之
那么對于當前的x，其實我們可以把所有的a分為m類
同一類的a對于x來說就是等價的
跑trie樹可以得到每一類的個數，設為f[0-(m-1)]吧

然后就是考慮如何計算貢獻
按題目要求的前面有x人時的貢獻為x²
而這個值恰好就是前面所有人任意組合可顛倒可與自己匹配的組合對數
什么意思呢？舉個例子
假如當前x前面有1 3 4，答案是9
對應的組合就是：

1 1
1 3
1 4
3 1
3 3
3 4
4 1
4 3
4 4

這有什么意義嗎？有的！
它可以幫助本題的轉化
只考慮 f_i 和 f_j 那么它們同時在x前面的天數應該是2^(m-2)
而根據剛才配對的性質，它們同時在前面對答案的貢獻是：

2* f_i * f_j

所以其總共的貢獻就是：

2^(m-2) * 2* f_i * f_j

然后枚舉ij累加再一起即可

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long typedef unsigned long long ull; const int N = 2e5+100; const int M=1e6+10; const ll mod=1e9+7; int n,m; int tr[N*30][2],tot=1,num[30*N]; int s[31],a[N],mi[31]; int now[31]; void build(int k){for(int i=30;i>=0;i--){s[i]=a[k]&mi[i]?1:0;}int p=1;for(int i=30;i>=0;i--){if(!tr[p][s[i]]) tr[p][s[i]]=++tot;p=tr[p][s[i]];num[p]++; } }void ask(int k){for(int i=30;i>=0;i--){s[i]=a[k]&mi[i]?1:0;}int p=1;for(int i=30;i>=0;i--){if(!tr[p][s[i]]) tr[p][s[i]]=++tot;now[i]=num[tr[p][!s[i]]];p=tr[p][s[i]];} } int main(){mi[0]=1;for(int i=1;i<=30;i++) mi[i]=mi[i-1]<<1;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&a[i]);build(i);}ll ans=0;for(int i=1;i<=n;i++){ask(i);double tot=0,pre=0;for(int j=0;j<=30;j++){tot+=0.5*(now[j]*now[j]+2*pre*now[j]);//if(now[j]) printf(" j=%d now=%d tot=%lf pre=%lf\n",j,now[j],tot,pre);pre+=0.5*now[j];}//printf("i=%d tot=%lf\n",i,tot);ans^=(ll)(tot*mi[m])%mod;}printf("%lld",ans);return 0; } /* 9 6 10 5 6 2 10 10 7 3 2 9 1 4 4 3 2 16 4 10 3 5 2 7 1 9 3 8 2 10 */

總結

以上是生活随笔為你收集整理的YBTOJ：运动积分（trie树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。