做卷闸门网站有用吗,seo顾问服务 乐云践新专家,东莞网络优化公司,贴吧做网站文章目录题目描述解析代码题目描述 解析
做了巨长时间… 进行了一次刺激的阅读理解竞赛… 感谢whh dalao#xff01; 那么让我们分析一下这道题 首先我们考虑单个求x选手的q值 不难发现 i 在第j天和x的大小关系只与a[x]与a[i]二进制下不同的最高位k有关 j的第k位与x相同时 那么让我们分析一下这道题 首先我们考虑单个求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人时的贡献为x2 而这个值恰好就是前面所有人任意组合可颠倒可与自己匹配的组合对数 什么意思呢举个例子 假如当前x前面有1 3 4答案是9 对应的组合就是 1 1 1 3 1 4 3 1 3 3 3 4 4 1 4 3 4 4 这有什么意义吗有的 它可以帮助本题的转化 只考虑 fi 和 fj 那么它们同时在x前面的天数应该是2(m-2) 而根据刚才配对的性质它们同时在前面对答案的贡献是 2* fi * fj 所以其总共的贡献就是 2(m-2) * 2* fi * fj 然后枚举ij累加再一起即可
代码
#includebits/stdc.h
using namespace std;
#define ll long long
typedef unsigned long long ull;
const int N 2e5100;
const int M1e610;
const ll mod1e97;
int n,m;
int tr[N*30][2],tot1,num[30*N];
int s[31],a[N],mi[31];
int now[31];
void build(int k){for(int i30;i0;i--){s[i]a[k]mi[i]?1:0;}int p1;for(int i30;i0;i--){if(!tr[p][s[i]]) tr[p][s[i]]tot;ptr[p][s[i]];num[p]; }
}void ask(int k){for(int i30;i0;i--){s[i]a[k]mi[i]?1:0;}int p1;for(int i30;i0;i--){if(!tr[p][s[i]]) tr[p][s[i]]tot;now[i]num[tr[p][!s[i]]];ptr[p][s[i]];}
}
int main(){mi[0]1;for(int i1;i30;i) mi[i]mi[i-1]1;scanf(%d%d,n,m);for(int i1;in;i){scanf(%d,a[i]);build(i);}ll ans0;for(int i1;in;i){ask(i);double tot0,pre0;for(int j0;j30;j){tot0.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);pre0.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
*/
