题解 | H题

这题用dp来解决

关键思路是,对于一段完全不重叠(所有数彼此相与都为0,以后简称合法)的序列[l,i] dp[i]=dp[l-1]+dp[l]+...+dp[i-1],也就是sum[i-1]-sum[l-2]

为什么?

我们一步一步来推导

假设一段序列 a1+a2+a3+a4+a5+a6 其中a3~a6是a6往前最长的合法序列, 假设dp[0]~dp[5]已经确定好了,那么,对于a5和a6之间的符号有两种情况

1:'+',就是dp[5]

2:'|',由于'|'的优先级比较高,这势必会对之前产生影响(比如a2和a3本来可以合并,和现在不能了), 这样我们只能接着向前讨论,也就是a4和a5之间的符号

1:'+',dp[4]

2:'|',显然.要接着向前讨论,直到a2和a3之间的符号,很明显的,a2和a3只能有'+',因此加到a2就结束了

因此dp[6]=dp[2]+...+dp[5]

接着我们如何快速确定最长的合法区间呢?

就是使用一个左指针l,和cur(表示前一个数的最长合法序列的或),cur如果和a[i]的与不为0,那我们就将a[l]从cur去掉,直到cur&a[i]=0

至于怎么从cur去掉,使用异或即可

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 998244353
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<ll>a(n+1,0);
        vector<ll>dp(n+1,0);
        vector<ll>sum(n+1,0);
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        dp[0]=1;
        sum[0]=1;
        int l=1;
        ll cur=0;
        for(int i=1;i<=n;i++){
            while(l<=i&&((cur&a[i])!=0)){
                cur^=a[l++];
            }
            cur|=a[i];
            if(l==1){
                dp[i]=sum[i-1];
                sum[i]=(dp[i]+sum[i-1])%mod;
            }
            else {
                dp[i]=(sum[i-1]-sum[l-2]+mod)%mod;
                sum[i]=(dp[i]+sum[i-1])%mod;
            }
        }
        cout<<dp[n]<<"\n";
    }
}

时间复杂度:O(n)

空间复杂度:O(n)