二进制拆位
题意：给定一个数组，求所有子区间的区间异或和的sum
Sol：先做异或前缀和，原问题则变成求数组中任意两个数的异或，然后全部相加起来的结果。我们考虑每个元素每位的贡献，只需要统计前面（偏序计数）有多少个数的本位与自己不同。
//这个题目显然应该作为模板题，似乎没有找到直白的在原数组上作拆位前缀和
//本题先通过异或前缀和预处理，来将问题转化为两两之间的异或和，
//如果不转化，就需要计算贡献次数
void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)a[i]^=a[i-1];
vector<int>c0(len+2,1),c1(len+2,0);
int ans=0;
for(int i=1;i<=n;i++){
int u=a[i];
for(int j=len;j>=0;j--){
if((u>>j)&1){
ans+=(1<<j)*c0[j];
c1[j]++;
}
else {
ans+=(1<<j)*c1[j];
c0[j]++;
}
}
}
cout<<ans<<endl;
}
链接：https://ac.nowcoder.com/acm/contest/65051/D
小美定义一个数组的权值为：数组中任选两个数的异或之和。例如，数组[2,1,3]的权值为：(2 xor 1)+(2 xor 3)+(1 xor 3)=3+1+2=6。 小美拿到了一个数组，她想知道该数组的所有连续子数组的权值和是多少？答案对\(10^9+7\)取模。
Sol：注意题目意思。一个子数组的权值是两两异或和，那么求所有子数组的权值和。考虑继续按位算贡献，对于枚举到当前数a[i]，我们计算他和每个前面的数计算的次数，当\(a[j](j<i)\)可以和其异或产生\(1<<k\)的贡献的时候,左端点有j个，右端点有n-i+1个，所以累加答案\(2^k\times j \times (n-i+1)\).那么我们需要预处理些什么呢？当前i，k是枚举的，我们显然不能枚举j，所以我们需要提前预处理有关j的前缀和，为什么能这样做的推导\(2^k\times j_1 \times (n-i+1)+2^k\times j_2 \times (n-i+1)=2^k\times (j_1+j_2) \times (n-i+1)\)。也就是说我们需要对于每一位记录0和1的下标前缀和
const int len = 30;
const int mod = 1e9 + 7;
vector<int>b0(40), b1(40);
void solve() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = len; j >= 0; j--) {
int u = (a[i] >> j) & 1;
if (u == 1) {
b1[j]+=i;b1[j]%=mod;
ans += b0[j] * (n - i + 1) % mod * (1LL << j) % mod;
ans %= mod;
} else {
b0[j]+=i;b0[j]%=mod;
ans += b1[j] * (n - i + 1) % mod * (1LL << j) % mod;
ans %= mod;
}
}
}
cout << ans << endl;
}
https://www.luogu.com.cn/problem/CF1879D Sum of XOR Functions
有一个序列 \(a\)，计算 $\sum\limits_{l=1}{n}\sum\limits_{r=l}n(r-l+1)\times \bigoplus\limits_{i=l}^{r}a_i $。
Sol：继续考虑贡献，枚举r，拆位前缀和维护符合要求下标L之和以及L的数量。不能全部开longlong，本题空间很紧张，不然会直接MLE.由于我们我们寻找的是所有在前缀和中能当左式的，本身就是L-1了，所以原本区间长度的减1就不用考虑了。
ll pre[N][30+2][2];
int num[N][30+2][2];
void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)a[i]^=a[i-1];
for(int j=0;j<=30;j++){
num[0][j][0]=1;
}
for(int i=1;i<=n;i++){
for(int j=0;j<=30;j++){
int u=(a[i]>>j)&1;
num[i][j][u]++;
num[i][j][u^1]=num[i-1][j][u^1];
num[i][j][u]+=num[i-1][j][u];
pre[i][j][u]+=i;
pre[i][j][u]+=pre[i-1][j][u];
pre[i][j][u]%=mod;
pre[i][j][u^1]=pre[i-1][j][u^1];
}
}
ll ans=0;
//枚举r，看有多少个L-1，
for(int i=1;i<=n;i++){
//bug(i);cerr<<endl;//
for(int j=0;j<=30;j++){
int u=(a[i]>>j)&1;
ll cnt=num[i-1][j][u^1];
// bug(j);bug(cnt);
// cerr<<endl;
ll tmp=cnt*(i)-pre[i-1][j][u^1];tmp%=mod;tmp+=mod;tmp%=mod;
ans=(ans+tmp*(1LL<<j)%mod)%mod;
}
}
cout<<ans<<endl;
}
给定一个数组，求 \(\sum_{i=1}^n\sum_{j=1}^n(a_i\oplus a_j)^2\)G. 沃托里村 - 2023 年（第十五届）四川省大学生程序设计大赛重现赛 - ECNU Online Judge
Sol：本题需要考虑平方的特性,直接拆位以后，看2的次幂的贡献，考虑指数运算法则，只需要记录00，01，10，11的对数就可以了，本题不要求偏序，直接全部考虑不用去重。
dbeug：注意乘法与取模同等优先级，从左到右算，所以需要对于出现1<<60的式子需要先打括号取模，再计算。也可以预处理2的次幂mod意义下的。
int pre[N];
int dp[M][2][M][2];
void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
pre[0]=1;
for(int i=1;i<=63;i++)pre[i]=pre[i-1]*2%mod;
for(int i=1;i<=n;i++){
for(int j=0;j<=30;j++){
for(int k=0;k<=30;k++){
int u1=(a[i]>>j)&1;
int u2=(a[i]>>k)&1;
dp[j][u1][k][u2]++;
}
}
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=0;j<=30;j++){
for(int k=0;k<=30;k++){
int u1=(a[i]>>j)&1;
int u2=(a[i]>>k)&1;
ans=(ans+dp[j][u1^1][k][u2^1]%mod*(1LL<<(j+k))%mod)%mod;
}
}
}
cout<<ans<<endl;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10, mod = 998244353;
LL a[N], pre[N], suf[N], s[N];
LL bit[2][35];
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
s[i] = s[i - 1] ^ a[i];
}
for (int i = 0; i <= 30; i++) {
bit[0][i]++;
}
for (int i = 1; i <= n; i++) {
pre[i] = pre[i - 1];
for (int j = 0; j <= 30; j++) {
int u = s[i] >> j & 1;
pre[i] = (pre[i] + (1 << j) * bit[u ^ 1][j] % mod) % mod;
}
for (int j = 0; j <= 30; j++) {
int u = s[i] >> j & 1;
bit[u][j]++;
}
}
memset(bit, 0, sizeof bit);
for (int i = 0; i <= 30; i++) {
bit[0][i]++;
}
for (int i = n; i >= 1; i--) {
s[i] = s[i + 1] ^ a[i];
}
for (int i = n; i >= 1; i--) {
suf[i] = suf[i + 1];
for (int j = 0; j <= 30; j++) {
int u = s[i] >> j & 1;
suf[i] = (suf[i] + (1 << j) * bit[u ^ 1][j] % mod) % mod;
}
for (int j = 0; j <= 30; j++) {
int u = s[i] >> j & 1;
bit[u][j]++;
}
}
memset(bit, 0, sizeof bit);
LL ans = 0;
for (int i = n; i >= 1; i--) {
for (int j = 0; j <= 30; j++) {
int u = s[i] >> j & 1;
ans = (ans + pre[i - 1] * (1 << j) % mod * bit[u ^ 1][j] % mod) % mod;
}
for (int j = 0; j <= 30; j++) {
int u = s[i] >> j & 1;
bit[u][j] = (bit[u][j] + suf[i]) % mod;
}
}
cout << ans << '\n';
return 0;
}
https://codeforces.com/problemset/problem/1878/E按位与的拆位前缀和
有 \(t\) 组数据。每组数据给定长度为 \(n\) 的数组 \(a\) 和 \(q\) 次询问。我们定义 \(\operatorname{f}(l,r)(1\le l\le r\le n)\) 表示 \(a_l\And a_{l+1}\& \dots\& a_{r-1}\&a_r\) 的结果。其中，\(\&\) 表示位与运算。对于每次询问，将给定 \(l,k\)。请你找到最大的 \(r\) 使得 \(\operatorname{f}(l,r)\ge k\)。如果无解，输出 -1。
Sol：考虑与运算具有递减性，所以可以二分r。考虑怎么check。由于与运算不可逆，无法像异或那样快速求出按位与的区间和，我们只能预处理拆位的前缀和，然后每次花费O(logn)的时间去计算区间与和。具体就是看每一位1的个数是不搜等于区间长度，因为只要有1个0就是0了。时间复杂度：\(O(mlogn^2)\)
int a[N];
//考虑预处理后花费O（log）求出区间与的和
void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
vector<vector<int>>pre(n+1,vector<int>(32,0));
for(int i=1;i<=n;i++){
for(int j=30;j>=0;j--){
int u=(a[i]>>j)&1;
if(u==1)pre[i][j]=1+pre[i-1][j];
else pre[i][j]=pre[i-1][j];
}
}
cin>>m;
for(int i=1;i<=m;i++){
int ql,k;cin>>ql>>k;
int l=ql;int r=n;
auto check=[&](int x){
int res=0;
for(int j=30;j>=0;j--){
if(pre[x][j]-pre[ql-1][j]==(x-ql+1))res+=(1<<j);
}
if(res>=k)return true;
return false;
};
if(a[ql]<k){cout<<-1<<" ";continue;}
while(l<r){
int mid=(l+r+1)>>1;
if(check(mid))l=mid;
else r=mid-1;
}
cout<<l<<" ";
}
cout<<endl;
}
https://vjudge.net/contest/602096#problem/E
给定一棵树，带边权，m次询问，每次给出l,r,x\(\sum_{i=l}^rxordist(i,x)\)，xordist为i到x上的路径异或起来。
Sol:考虑单点对单点的时候，钦定1为根不影响答案。算一下树上前缀和d[x].则答案就是d[i]^d[x].现在就是考虑多个数与一个数的异或和，我们需要在logn的时间内求出。预处理按位的0和1的数量，直接按每一位的贡献和数量计算。
int a[N];
#define a2 array<int,2>
struct edge{int v,w;};
vector<edge>e[N];
int d[N];
void dfs(int u,int fa){
for(auto [v,w]:e[u]){
if(v==fa)continue;
d[v]=d[u]^w;
dfs(v,u);
}
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++){d[i]=0;e[i].clear();}
for(int i=1;i<=n-1;i++){
int u,v,w;cin>>u>>v>>w;
e[u].push_back({v,w});
e[v].push_back({u,w});
}
// for(int i=1;i<=n;i++)bug(d[i]);
dfs(1,0);
// for(int i=1;i<=n;i++)bug(d[i]);
cin>>m;
//for(int i=1;i<=n;i++)s[i]=d[i]^s[i-1];
vector<vector<a2>> pre(n+1, vector<a2>(31, a2()));
for(int i=1;i<=n;i++){
for(int j=0;j<=30;j++){
int u=(d[i]>>j)&1;
pre[i][j][u]=pre[i-1][j][u]+1;
pre[i][j][u^1]=pre[i-1][j][u^1];
}
}
for(int i=1;i<=m;i++){
int l,r,x;cin>>l>>r>>x;
int ans=0;
for(int j=0;j<=30;j++){
int u=(d[x]>>j)&1;
int cnt=pre[r][j][u^1]-pre[l-1][j][u^1];
ans=(ans+cnt*(1LL<<j));
}
cout<<ans<<endl;
}
}
非常遗憾调试失败，还要赶进度，以后再回来吧
给定一个数组，求\(\sum_{l=1}^n\sum_{r=l}^n(a_l\bigoplus a_{l+1}\bigoplus \dots\bigoplus a_r)\times\min_{l\leq i\leq r}a_i\)
先用单调栈套路地得到左右边界，对于左右边界，统计左0右1地个数，左1右0个数，然后考虑拆位前缀和算贡献，思路不难，注意注意边界处理。
全局开了longlong，依然不知道wa哪里了
// Problem: I - 序列
// Contest: Virtual Judge - 2023杭电新生赛
// URL: https://vjudge.net/contest/602096#problem/I
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
# define int long long
#define ull unsigned long long
#define pii pair<int,int>
#define db double
#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl "\n"
#define alls(x) (x).begin(), (x).end()
#define fs first
#define sec second
#define bug(x) cerr << #x << " = " << x << endl
#define bug2(x) cerr << #x << " = " << x <<" "
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
const double PI = acos(-1.0);
int n, m;
#define a2 array<int,2>
void solve(){
cin>>n;
vector<int>a(n+1);
for(int i=1;i<=n;i++)cin>>a[i];
stack<int>pre;
stack<int>nxt;
vector<int>l(n+1,0),r(n+1,0),s(n+1,0);
for(int i=1;i<=n;i++)s[i]=s[i-1]^a[i];
for(int i=1;i<=n;i++){
while(!pre.empty()&&a[i]<=a[pre.top()])pre.pop();
if(!pre.empty())l[i]=pre.top()+1;
else l[i]=1;
pre.push(i);
}
for(int i=n;i>=1;i--){
while(!nxt.empty()&&a[i]<=a[nxt.top()])nxt.pop();
if(!nxt.empty())r[i]=nxt.top()-1;
else r[i]=n;
nxt.push(i);
}
int ans=0;
// for(int i=1;i<=n;i++)cerr<<a[i]<<" ";
// cerr<<endl;
// for(int i=1;i<=n;i++)cerr<<l[i]<<" ";
// cerr<<endl;
// for(int i=1;i<=n;i++)cerr<<r[i]<<" ";
// cerr<<endl;
vector<vector<a2>>f(n+1,vector<a2>(32,a2()));
// for(int i=0;i<=30;i++)f[0][i][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=30;j++){
int u=(s[i]>>j)&1;
f[i][j][u]=1+f[i-1][j][u];
f[i][j][u^1]=f[i-1][j][u^1];
}
}
// for(int i=1;i<=n;i++)cerr<<s[i]<<" ";
// cerr<<endl;
// bug(f[3][0][1]);
// bug(f[3][1][1]);
// bug(f[3][2][1]);
// bug(f[0][0][1]);
// bug(f[0][1][1]);
// bug(f[0][2][1]);
for(int i=1;i<=n;i++){
int res=0;int ql=l[i],qr=r[i];
// bug(i);bug(l[i]);bug(r[i]);
for(int j=0;j<=30;j++){
int cl1,cl0;int cr1,cr0;
cr0=f[qr][j][0]-f[i-1][j][0];
cl0=f[i-1][j][0]-f[max(ql-2,0LL)][j][0];
cl1=f[i-1][j][1]-f[max(ql-2,0LL)][j][1];
cr1=f[qr][j][1]-f[i-1][j][1];
if(ql-1<=0)cl0++;
int cnt=cl1*cr0%mod+cl0*cr1%mod;cnt%=mod;
//bug2(cl1);bug2(cl0);bug2(cr1);bug2(cr0);
//bug(i);bug(j);bug(cnt);bug("___");
res=(res+cnt*((1LL<<j)%mod)%mod)%mod;
}
//bug(i);bug(res);
ans=(ans+(res*a[i])%mod)%mod;
}
cout<<ans<<endl;
}
signed main() {
cin.tie(0);
ios::sync_with_stdio(false);
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
//freopen("debug.txt", "w", stderr);
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
给一份std参考
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
const int mod=998244353;
int a[N],pre[N];
int prexors[40][N];
int stk[N];
int l[N],r[N];
int getres(int l,int r,int x)
{
int res=0;
for(int i=0;i<32;i++)
{
//vector<int> Lrange(2),Rrange(2);
int Lrange[2],Rrange[2];
Lrange[1]=prexors[i][x-1]-(l?prexors[i][l-1]:0);
Lrange[0]=x-l-Lrange[1];
Rrange[1]=prexors[i][r]-prexors[i][x-1];
Rrange[0]=r-x+1-Rrange[1];
int t=(Lrange[0]*Rrange[1]%mod+Lrange[1]*Rrange[0]%mod)%mod;
t=(t*(1ll<<i))%mod;
res=(res+t)%mod;
}
return res;
}
void kei()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int tt=0;
for(int i=1;i<=n;i++)
{
while(tt&&a[stk[tt]]>a[i])tt--;
l[i]=tt?stk[tt]:0;
stk[++tt]=i;
}
tt=0;
for(int i=n;i>=1;i--)
{
while(tt&&a[stk[tt]]>=a[i])tt--;
r[i]=tt?stk[tt]-1:n;
stk[++tt]=i;
}
for(int i=1;i<=n;i++)pre[i]=pre[i-1]^a[i];
for(int i=1;i<=n;i++)for(int j=0;j<32;j++)prexors[j][i]=(pre[i]>>j)&1;
for(int i=0;i<32;i++)for(int j=1;j<=n;j++)prexors[i][j]+=prexors[i][j-1];
int res=0;
for(int i=1;i<=n;i++)res=(res+getres(l[i],r[i],i)*a[i]%mod)%mod;
cout<<res<<'\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
int t=1;
cin>>t;
while(t--)kei();
}
https://ac.nowcoder.com/acm/discuss/blogs?tagId=268078
https://ac.nowcoder.com/acm/contest/80793/D
标签：pre,二进制,tt,int,ans,--,拆位,mod From： https://www.cnblogs.com/mathiter/p/18199393