数学、动态规划

这么简单的题赛时没做出来，不应该。发现题目的值域特殊应该考虑复杂度依赖值域的做法。

由于 $a_i \leq 1023$，任取 $a$ 的一个子集，这个子集的异或和也不可能超过 $1023$。

设计 $dp_{i,j}$ 表示前 $i$ 个数得到的异或和为 $j$ 的概率，状态有 $O(nV)$ 个，滚动数组优化掉 $i$ 这一维。题目卡常，下面的代码在最初代码的基础上进行轻微改动，减少 $4nV$ 次乘法运算后才能通过。如果追求效率，可以放弃封装好的取模类。

时间复杂度 $O(nV)$。

#include<bits/stdc++.h>
using namespace std;
constexpr int lim=1'023,V=10'000,mod=1'000'000'007;
Mint<mod> ans,f[10'005],dp[2][1'025];
int n,a[200'005],p[200'005];
void solution(){
    cin>>n,ans=0;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>p[i];
    for(int i=0;i<=lim;i++) dp[0][i]=0,dp[1][i]=0;
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=lim;j++)
            dp[i&1][j]=dp[(i&1)^1][j]*f[V-p[i]]+dp[(i&1)^1][j^a[i]]*f[p[i]];
    for(int i=0;i<=lim;i++) ans+=dp[n&1][i]*i*i;
    cout<<ans<<'\n';
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    for(int i=1;i<=V;i++) f[i]=i/Mint<mod>(V);
    cin>>T;
    while(T--) solution();
    return 0;
}