2023NOIP A层联测26

给定 n n n 个整数 a 1 , a 2 … a n a_1,a_2\dots a_n a1​,a2​…an​，求
∑ i = 1 n ∑ j = i n ( ⨁ k = i j a k ) 2 \sum\limits_{i=1}^n\sum\limits_{j=i}^n\left(\bigoplus\limits_{k=i}^{j}a_k\right)^2 i=1∑n​j=i∑n​(k=i⨁j​ak​)2

答案模 998244353 998244353 998244353。

n , a i ≤ 2 × 1 0 5 n,a_i\le2\times10^5 n,ai​≤2×105。

不会题解的做法，提供一个我赛时的做法。

S i S_i Si​ 是 a i a_i ai​ 的前缀异或和，答案就是 ∑ i = 1 n ∑ j = i n ( S i − 1 ⊕ S j ) 2 \sum\limits_{i=1}^n\sum\limits_{j=i}^n(S_{i-1}\oplus S_j)^2 i=1∑n​j=i∑n​(Si−1​⊕Sj​)2

为了后面方便处理，答案还可表示为 1 2 ∑ i = 0 n ∑ j = 0 n ( S i ⊕ S j ) 2 \frac12\sum\limits_{i=0}^n\sum\limits_{j=0}^n(S_i\oplus S_j)^2 21​i=0∑n​j=0∑n​(Si​⊕Sj​)2

容易想到 F W T FWT FWT。直接设 m = 2 18 − 1 m=2^{18}-1 m=218−1， b i = ∑ j = 0 m [ S j = i ] b_i=\sum\limits_{j=0}^m[S_j=i] bi​=j=0∑m​[Sj​=i]

算出 c = b ∗ b c=b*b c=b∗b，此时 c k c_k ck​ 就为 S i ⊕ S j = k S_{i}\oplus S_{j}=k Si​⊕Sj​=k 的个数。

答案就是 1 2 ∑ i = 0 m c i i 2 \frac12\sum\limits_{i=0}^mc_ii^2 21​i=0∑m​ci​i2

时间复杂度 O ( m log ⁡ m ) O(m\log m) O(mlogm)，其中 m m m 是值域，比题解优秀。

代码如下

#include<bits/stdc++.h>
using namespace std;
#define ll long long
constexpr ll mod=998244353,inv2=499122177;
const int N=2e5+1;
int a[N],sum[N],n;
ll ans,b[1<<18];
void f(ll a[],int len,int fl)
{for(int i=2;i<=len;i<<=1){for(int j=0;j<len;j+=i){for(int k=j;k<j+i/2;k++){ll num1=a[k],num2=a[k+i/2];if(fl==1){a[k]=(num1+num2)%mod;a[k+i/2]=(num1-num2+mod)%mod;}else{a[k]=(num1+num2)*inv2%mod;a[k+i/2]=(num1-num2+mod)*inv2%mod;}}}}
}
int main()
{freopen("origen.in","r",stdin);freopen("origen.out","w",stdout);cin.tie(0)->sync_with_stdio(0);cin>>n;b[0]++;for(int i=1;i<=n;i++) cin>>a[i],sum[i]=sum[i-1]^a[i],b[sum[i]]++;int len=1<<18;f(b,len,1);for(int i=0;i<len;i++) b[i]=b[i]*b[i]%mod;f(b,len,-1);for(int i=0;i<len;i++) ans=(ans+1ll*i*i%mod*b[i])%mod;cout<<ans*inv2%mod;
}

2023NOIP A层联测26

给定 n n n 个整数 a 1 , a 2 … a n a_1,a_2\dots a_n a1​,a2​…an​，求
∑ i = 1 n ∑ j = i n ( ⨁ k = i j a k ) 2 \sum\limits_{i=1}^n\sum\limits_{j=i}^n\left(\bigoplus\limits_{k=i}^{j}a_k\right)^2 i=1∑n​j=i∑n​(k=i⨁j​ak​)2

答案模 998244353 998244353 998244353。

n , a i ≤ 2 × 1 0 5 n,a_i\le2\times10^5 n,ai​≤2×105。

不会题解的做法，提供一个我赛时的做法。

S i S_i Si​ 是 a i a_i ai​ 的前缀异或和，答案就是 ∑ i = 1 n ∑ j = i n ( S i − 1 ⊕ S j ) 2 \sum\limits_{i=1}^n\sum\limits_{j=i}^n(S_{i-1}\oplus S_j)^2 i=1∑n​j=i∑n​(Si−1​⊕Sj​)2

为了后面方便处理，答案还可表示为 1 2 ∑ i = 0 n ∑ j = 0 n ( S i ⊕ S j ) 2 \frac12\sum\limits_{i=0}^n\sum\limits_{j=0}^n(S_i\oplus S_j)^2 21​i=0∑n​j=0∑n​(Si​⊕Sj​)2

容易想到 F W T FWT FWT。直接设 m = 2 18 − 1 m=2^{18}-1 m=218−1， b i = ∑ j = 0 m [ S j = i ] b_i=\sum\limits_{j=0}^m[S_j=i] bi​=j=0∑m​[Sj​=i]

算出 c = b ∗ b c=b*b c=b∗b，此时 c k c_k ck​ 就为 S i ⊕ S j = k S_{i}\oplus S_{j}=k Si​⊕Sj​=k 的个数。

答案就是 1 2 ∑ i = 0 m c i i 2 \frac12\sum\limits_{i=0}^mc_ii^2 21​i=0∑m​ci​i2

时间复杂度 O ( m log ⁡ m ) O(m\log m) O(mlogm)，其中 m m m 是值域，比题解优秀。

代码如下

#include<bits/stdc++.h>
using namespace std;
#define ll long long
constexpr ll mod=998244353,inv2=499122177;
const int N=2e5+1;
int a[N],sum[N],n;
ll ans,b[1<<18];
void f(ll a[],int len,int fl)
{for(int i=2;i<=len;i<<=1){for(int j=0;j<len;j+=i){for(int k=j;k<j+i/2;k++){ll num1=a[k],num2=a[k+i/2];if(fl==1){a[k]=(num1+num2)%mod;a[k+i/2]=(num1-num2+mod)%mod;}else{a[k]=(num1+num2)*inv2%mod;a[k+i/2]=(num1-num2+mod)*inv2%mod;}}}}
}
int main()
{freopen("origen.in","r",stdin);freopen("origen.out","w",stdout);cin.tie(0)->sync_with_stdio(0);cin>>n;b[0]++;for(int i=1;i<=n;i++) cin>>a[i],sum[i]=sum[i-1]^a[i],b[sum[i]]++;int len=1<<18;f(b,len,1);for(int i=0;i<len;i++) b[i]=b[i]*b[i]%mod;f(b,len,-1);for(int i=0;i<len;i++) ans=(ans+1ll*i*i%mod*b[i])%mod;cout<<ans*inv2%mod;
}