T1
把 \(a_i\) 前缀和，式子就变成了 \(\sum_{i=0}^n\sum_{j=i+1}^na_i\oplus a_j\)，我们把这些贡献看成 \(a_j\) 的贡献。
然后按位考虑，那么一个数的平方就拆成了一些数加和的平方，拆开就会变成一些数的平方，和一些数的乘积的二倍。考虑分开计算这两部分的贡献。
枚举每个数 \(x\)，设 \(f_{i,0/1,j,0/1}\) 表示在 \(x\) 之前的所有数中，在二进制下第 \(i\) 位为 \(0/1\)，且第 \(j\) 位为 \(0/1\) 的数的个数。看有多少个数会和当前位产生贡献。
枚举 \(x\) 的每一位，设当前位为 \(k1\)，这一位上的数为 \(p1\)。对于第一部分，前面的数有的会和他产生 \((2^k)^2\) 的贡献，这样的数有 \(f_{k1,p1\oplus1,k1,p1\oplus1}\) 个。对于第二部分，还会产生 \(2\times 2^{k1} \times 2^{k2}\) 的贡献，枚举 \(k2\)，产生这个贡献的数的个数为
\(f_{k1,p1\oplus1,k2,p2\oplus1}\)，全部加起来就好了。
复杂度为 \(\Theta(n\log^2 n)\)
Code
#include <iostream>
#include <cstdio>
#define int long long
const int N=2e5+10;
const int M=20;
const int mod=998244353;
using namespace std;
inline int read() {
int f=1, x=0;
char ch=getchar();
while(ch>'9' || ch<'0') {
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9') {
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return f*x;
}
inline void write(int x) {
cout<<x; putchar('\n');
}
int n, tot;
int a[N], power[M];
int f[M][2][M][2];
signed main() {
n=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) a[i]^=a[i-1];
for(int i=1;i<=18;i++) {
for(int j=1;j<=18;j++) {
f[i][0][j][0]=1;
}
}
power[0]=1;
for(int i=1;i<=18;i++) {
power[i]=(power[i-1]*2ll)%mod;
}
int ans=0;
for(int i=1;i<=n;i++) {
for(int j=1;j<=18;j++) {
int p1=((a[i]>>(j-1)) & 1);
ans=(ans+power[j-1]*power[j-1]%mod*f[j][p1^1][j][p1^1]%mod)%mod;
for(int k=j+1;k<=18;k++) {
int p2=((a[i]>>(k-1)) & 1);
ans=(ans+2ll*power[j-1]%mod*power[k-1]%mod*f[j][p1^1][k][p2^1]%mod)%mod;
}
}
for(int j=1;j<=18;j++) {
int p1=((a[i]>>(j-1)) & 1);
for(int k=1;k<=18;k++) {
int p2=((a[i]>>(k-1)) & 1);
f[j][p1][k][p2]++;
}
}
}
write(ans);
return 0;
}
T2
考虑统计所有子区间的贡献，最后除以概率就是期望。
如果不考虑重复的情况，那么答案就是 \(\sum_{i=1}^n(r_i-l_1+1)\times i\times (n-i+1)\)
那么考虑如何去掉重复的，设 \(pre_{i,j}\) 表示在第 \(i\) 个人之前，最后一个可以做出 \(j\) 题的人的位置，那么算重的个数即为 \(pre_{i,j}\times (n-i+1)\)
线段树维护 \(pre_{i,j}\) 即可。需要离散化，把每个端点单独看做一块就可以很好离散化了。
复杂度为 \(\Theta(n\log n)\)
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
const int N=1e6+10;
const int mod=1e9+7;
using namespace std;
inline int read() {
int f=1, x=0;
char ch=getchar();
while(ch>'9' || ch<'0') {
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9') {
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return f*x;
}
inline void write(int x) {
cout<<x; putchar('\n');
}
namespace Mudrock_mod {
inline int add(int x, int y) { return x + y >= mod ? x + y - mod : x + y; }
inline int del(int x, int y) { return x >= y ? x - y : x - y + mod; }
inline int mul(int x, int y) { return x * y % mod; }
inline void Add(int &x, int y) { x = x + y >= mod ? x + y - mod : x + y; }
inline void Del(int &x, int y) { x = x >= y ? x - y : x - y + mod; }
inline void Mul(int &x, int y) { x = 1ll * x * y % mod; }
}
using namespace Mudrock_mod;
int n, m, ans, tot, Len;
struct node {
int l, r;
}a[N];
int mp[N<<1], len[N<<2];
struct Seg_Tree {
struct Tree {
int sum, tag, len;
}t[N<<4];
inline void push_up(int k) {
t[k].sum=add(t[k<<1].sum, t[k<<1|1].sum);
t[k].len=add(t[k<<1].len, t[k<<1|1].len);
}
inline void push_down(int k) {
if(!t[k].tag) return;
t[k<<1].sum=mul(t[k].tag, t[k<<1].len);
t[k<<1|1].sum=mul(t[k].tag, t[k<<1|1].len);
t[k<<1].tag=t[k<<1|1].tag=t[k].tag;
t[k].tag=0;
}
void build(int k,int l,int r) {
if(l==r) {
t[k].len=len[l];
t[k].sum=0;
return;
}
int mid=(l+r)>>1;
build(k<<1, l, mid);
build(k<<1|1, mid+1, r);
push_up(k);
}
void up_date(int k,int l,int r,int L,int R,int val) {
if(L<=l && r<=R) {
t[k].sum=mul(t[k].len, val);
t[k].tag=val;
return;
}
push_down(k);
int mid=(l+r)>>1;
if(L<=mid) up_date(k<<1, l, mid, L, R, val);
if(R>mid) up_date(k<<1|1, mid+1, r, L, R, val);
push_up(k);
}
int query(int k,int l,int r,int L,int R) {
if(L<=l && r<=R) return t[k].sum;
push_down(k);
int mid=(l+r)>>1, res=0;
if(L<=mid) Add(res, query(k<<1, l, mid, L, R));
if(R>mid) Add(res, query(k<<1|1, mid+1, r, L, R));
return res;
}
}T;
inline int fpow(int x,int k) {
x%=mod;
int res=1;
while(k) {
if(k&1) res=res*x%mod;
x=x*x%mod;
k>>=1;
}
return res%mod;
}
inline int inv(int x) {
return fpow(x%mod, mod-2)%mod;
}
inline int id(int x) {
return x*2-1;
}
signed main() {
freopen("competition.in","r",stdin);
freopen("competition.out","w",stdout);
n=read(), m=read();
for(int i=1;i<=n;i++) {
int l=read(), r=read();
a[i]=(node){l, r};
mp[++tot]=l, mp[++tot]=r;
Add(ans, mul((r-l+1)%mod, mul(i, n-i+1)));
}
sort(mp+1,mp+tot+1);
tot=unique(mp+1, mp+tot+1)-mp-1;
for(int i=1;i<=n;i++) {
a[i].l=lower_bound(mp+1, mp+tot+1, a[i].l)-mp;
a[i].r=lower_bound(mp+1, mp+tot+1, a[i].r)-mp;
}
for(int i=1;i<tot;i++) {
len[(i<<1)-1]=1;
len[(i<<1)]=(mp[i+1]-mp[i]-1)%mod;
}
len[(tot<<1)-1]=1;
int Len=(tot<<1)-1;
T.build(1, 1, Len);
for(int i=1;i<=n;i++) {
int val=T.query(1, 1, Len, id(a[i].l), id(a[i].r))%mod;
ans=(ans+mod-val*(n-i+1)%mod)%mod;
T.up_date(1, 1, Len, id(a[i].l), id(a[i].r), i);
}
ans=(ans*inv(n*(n+1)/2))%mod;
write(ans);
return 0;
}