2023NOIP A层联测26-origen

本文主要是介绍2023NOIP A层联测26-origen，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给定 $n$ 个整数 $a_1,a_2\dots a_n$，求
$$\sum _{i=1}^n\sum _{j=i}^n{\left(\underset{k=i}{\overset{j}{⨁}}{a}_k\right)}^2$$

答案模 $998244353$。

$n,a_i\le 2\times 10^5$。

---

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

$S_i$ 是 $a_i$ 的前缀异或和，答案就是 $\sum _{i=1}^n\sum _{j=i}^n(S_{i-1}\oplus S_j{)}^2$

为了后面方便处理，答案还可表示为 $\frac{1}{2}\sum _{i=0}^n\sum _{j=0}^n(S_i\oplus S_j{)}^2$

容易想到 $FWT$。直接设 $m=2^{18}-1$，$b_i=\sum _{j=0}^m[S_j=i]$

算出 $c=b\ast b$，此时 $c_k$ 就为 $S_i\oplus S_j=k$ 的个数。

答案就是 $\frac{1}{2}\sum _{i=0}^m{c}_i{i}^2$

时间复杂度 $O(m\log 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-origen的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---