题目链接
题意:
给定一个长度为 n 的序列 a[1..n]，定义函数 f(b[1..m]) 的值为在 [0,m-1] 内满足如下条件的 i 的数目：
b 中前 i 个数异或起来的值小于 b 中前 i +1个数异或起来的值。
对于 a[1..n] 的每个子序列 b[1..m]，求f(b[1..m])之和。
思路:
这又是一个二进制的dp问题啊,这种东西一直是我的弱项,明知道需要分离每一位去转化,却搞不明白要求什么.
PS：这里说的子序列是可以不连续的.
对于ai,我们要知道a1....i-1有多少个子序列满足 a[i]^s>s.那么我们首先就需要明确,当a[i]为0,这两个数是相等的,
当a[i]的最高位为1的时候,s所对应的二进制必定为0(s为子序列的异或和).否则如果s的也为1,异或为0,必定使其值小于s
不满足.
所以,我们只需要找到a[i]最高位1为的位置,然后记录a[i]的子序列中对应这一位的和为0的种类数.这个可以用
一个dp来解决,dp[bit][j]表示第bit位异或和为j的子序列有多少种,（可以知道j只有0 1）,然后剩下的a[i]后面的数,每一个数
都取或不取,就有2^(n-i).
进行递推时的转化见代码/
#include<bits/stdc++.h> #define Ri(a) scanf("%d", &a) #define Rl(a) scanf("%lld", &a) #define Rf(a) scanf("%lf", &a) #define Rs(a) scanf("%s", a) #define Pi(a) printf("%d\n", (a)) #define Pf(a) printf("%lf\n", (a)) #define Pl(a) printf("%lld\n", (a)) #define Ps(a) printf("%s\n", (a)) #define W(a) while(a--) #define CLR(a, b) memset(a, (b), sizeof(a)) #define MOD 998244353 #define inf 0x3f3f3f3f #define exp 0.00000001 #define pii pair<int, int> #define mp make_pair #define pb push_back using namespace std; typedef long long ll; const int maxn=1e5+10; ll dp[66][5]; ll a[maxn]; int n; ll f[maxn]; void init() { CLR(f,0); f[0]=1; for(int i=1;i<maxn;i++) f[i]=f[i-1]*2%MOD; return ; } int main() { init(); Ri(n); for(int i=1;i<=n;i++) { Rl(a[i]); } for(int i=0;i<=31;i++) { dp[i][0]=1; dp[i][1]=0; } ll ans=0; int bit=0; for(int i=1;i<=n;i++) { for(bit=31;((a[i]>>bit)&1)==0;bit--);//找到a[i]最高位的1 ans=(ans+dp[bit][0]*f[n-i]%MOD)%MOD; for(bit=0;bit<32;bit++)//dp转移 { int x=dp[bit][0]; int y=dp[bit][1];//这里需要记录一下,因为下面的值会变. int w=(a[i]>>bit)&1; if(!w) { dp[bit][0]=(x*2)%MOD; dp[bit][1]=(y*2)%MOD; } else { dp[bit][0]=(x+y)%MOD; dp[bit][1]=(y+x)%MOD; } } } Pl(ans%MOD); return 0; } Marcus-Bao 认证博客专家 推荐系统 ACM算法竞赛 机器学习 本科毕业于国内知名四非大学，现中国科学院大学博士生，中国科学院计算技术研究所vipl实验室，老年ACM铁牌退役选手，喜欢算法竞赛，会点数据结构和算法，熟悉c++，python等；现阶段研究方向主要为机器学习与数据挖掘，比较关注推荐系统，发过顶会，炼过丹，平时博客主要记录些关于算法、数据结构，人工智能技术以及平时看的论文总结分享等，欢迎大家关注我，一起多多交流共同进步！
