异或(xor)

题目描述给定一个长度为n nn的序列a [ 1 … n ] a[1 \dots n]a[1…n]定义函数f ( b [ 1 … m ] ) f(b[1 \dots m])f(b[1…m])的值为在[ 0 , m − 1 ] [0, m-1][0,m−1]内满足如下条件的i ii的数目b bb中前i ii个数异或起来的值小于b bb中前i 1 i1i1个数异或起来的值。对于a [ 1 … n ] a[1 \dots n]a[1…n]的每个子序列b [ 1 … m ] b[1 \dots m]b[1…m]求f ( b [ 1 … m ] ) f(b[1 \dots m])f(b[1…m])之和答案对998244353 998244353998244353取模。输入格式第一行一个正整数n nn。接下来一行共n nn个整数a 1 , a 2 , … , a n a_1, a_2, \dots, a_na1​,a2​,…,an​。输出格式一个整数表示答案。样例输入151 2 3 4 5样例输出164数据规模共 10 个测试点。测试点 1,2 满足n ≤ 20 n \le 20n≤20。测试点 3,4 满足n ≤ 1000 n \le 1000n≤1000。测试点 5,6 满足a i ≤ 2 8 − 1 a_i \le 2^8 - 1ai​≤28−1。对于所有数据满足1 ≤ n ≤ 10 5 , 0 ≤ a i ≤ 2 30 − 1 1 \le n \le 10^5, 0 \le a_i \le 2^{30} - 11≤n≤105,0≤ai​≤230−1。详解思路启发我们先想一想什么时候一个数异或上另一个数后变大。设当前和为s u m sumsum新加入的数为x xx。那么对于x xx的前导 0它们不会使得s u m sumsum变化。但是我们发现对于x xx的最高位的1 11如果s u m sumsum这一位为 0那么我们就不用看后面了因为就算后面全部变小s u m sumsum也还是变大。s u m sumsum的这一位为1 11同理。那就很明显了我们求出a i a_{i}ai​最高位的 1设这一位为第k kk位那么我们只需统计前面的使得异或和的第k kk为 0 的方案数设这个为c n t i − 1 , k , 0 cnt_{i-1,k,0}cnti−1,k,0​很显然到这里前i ii个数都确定了后面的n − i n-in−i个数选不选入都不影响i ii产生贡献因而i ii位产生贡献为c n t i − 1 , k , 0 ⋅ 2 n − i cnt_{i-1,k,0}\cdot 2^{n-i}cnti−1,k,0​⋅2n−i。动态规划求取c n t i , j , 0 / 1 cnt_{i,j,0/1}cnti,j,0/1​这个很简单我们直接写状态转移。首先对于边界。题目说了i ii是可以取到 0 的因而 0 对每一位 0 都有 1 的贡献。c n t 0 , j , 0 ← 1 , j ∈ [ 0 , 30 ] cnt_{0,j,0}\leftarrow 1,j\in [0,30]cnt0,j,0​←1,j∈[0,30]虽说只有 30 位但实践中建议略大一点我取的 31。对于每个a i a_{i}ai​第i ii个数可选可不选。不选的时候有c n t i , j , 0 ← c n t i − 1 , j , 0 , c n t i , j , 1 ← c n t i − 1 , j , 1 , j ∈ [ 0 , 30 ] cnt_{i,j,0}\leftarrow cnt_{i-1,j,0},cnt_{i,j,1}\leftarrow cnt_{i-1,j,1},j\in [0,30]cnti,j,0​←cnti−1,j,0​,cnti,j,1​←cnti−1,j,1​,j∈[0,30]如果要选的时候则要看第j jj位是什么。当第j jj位为 0 的时候有c n t i , j , 0 ← c n t i − 1 , j , 0 , c n t i , j , 1 ← c n t i − 1 , j , 1 , j ∈ [ 0 , 30 ] cnt_{i,j,0}\leftarrow cnt_{i-1,j,0},cnt_{i,j,1}\leftarrow cnt_{i-1,j,1},j\in [0,30]cnti,j,0​←cnti−1,j,0​,cnti,j,1​←cnti−1,j,1​,j∈[0,30]你可能会问这和不选不是一模一样吗对就是一样的但这是 2 个方案不能省略。为 1 时有c n t i , j , 0 ← c n t i − 1 , j , 1 , c n t i , j , 1 ← c n t i − 1 , j , 0 , j ∈ [ 0 , 30 ] cnt_{i,j,0}\leftarrow cnt_{i-1,j,1},cnt_{i,j,1}\leftarrow cnt_{i-1,j,0},j\in [0,30]cnti,j,0​←cnti−1,j,1​,cnti,j,1​←cnti−1,j,0​,j∈[0,30]就是反过来。Code:#includebits/stdc.husingnamespacestd;#definelllonglongconstll N1e55,M35,mod998244353;ll n,a[N];ll cnt[N][M][2];ll ans0;llqpow(ll a,ll b){//快速幂ll res1;while(b){if(b1)resres*a%mod;aa*a%mod;b1;}returnres;}intmain(){cinn;for(ll i1;in;i)cina[i];for(ll i0;i31;i)cnt[0][i][0]1;for(ll i1;in;i){for(ll j0;j31;j){//dpcnt[i][j][0]cnt[i-1][j][0];cnt[i][j][1]cnt[i-1][j][1];if((a[i]j)1){cnt[i][j][1](cnt[i][j][1]cnt[i-1][j][0])%mod;cnt[i][j][0](cnt[i][j][0]cnt[i-1][j][1])%mod;}else{cnt[i][j][1](cnt[i][j][1]cnt[i-1][j][1])%mod;cnt[i][j][0](cnt[i][j][0]cnt[i-1][j][0])%mod;}}}for(ll i1;in;i){ll k31;while(((a[i]k)1)0k0)k--;//求这个数的最高位if(k-1)continue;//a[i]0 则一定没有贡献ans(ansqpow(2,n-i)%mod*cnt[i-1][k][0]%mod)%mod;}coutans;return0;}