CF1327F AND Segments

Description

你有三个整数以及个限制。

计算满足下列条件的，长度为的序列的个数：

对于每个，。
对于每个，数字的按位与。

两个序列被认为是不同的，当且仅当存在一个位置满足。

答案对取模。

。

Sol

按位与可以分解为个子问题，答案为子问题答案之积。

考虑转化限制：给定区间，区间内不能/必须有。

对于必须有的情况，预处理表示之间必须有。

表示前个位置，上一次填的位置为的方案数。

辅助定义：表示是否必须填。

转移：

看起来这个是的。想办法优化。

我们发现大量的转移都只是从上一层直接复制过来或者直接为，所以考虑先滚掉第一维。

然后进一步发现由于一定单调不减，故被刷为的部分一定是向右单调不减的。

考虑维护前缀和与一个指针表示当前，指针右移时在前缀和中删掉这一项的贡献，答案更新为前缀和即可。

时间复杂度。

Code

#include<bits/stdc++.h>
using std::vector;
#define int long long
typedef vector<int> vi;
typedef long long ll;
const int Mod=998244353;
template<typename Tp=int>inline Tp read(){Tp x(0);int op(0);char ch=getchar();while(ch<'0'||ch>'9')op|=(ch==45),ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return op?-x:x;}

signed main(){
    int n=read(),K=read(),m=read();
    vi L(m+1),R(m+1),X(m+1);
    for(int i=1;i<=m;++i)L[i]=read(),R[i]=read()+1,X[i]=read();
    auto solve=[&](vi a) -> int {
        vi lef(n+2),one(n+2);
        for(int i=1;i<=m;++i)
            if(a[i])one[L[i]]++,one[R[i]]--;
            else lef[R[i]]=std::max(lef[R[i]],L[i]);
        for(int i=2;i<=n+1;++i)one[i]+=one[i-1],lef[i]=std::max(lef[i],lef[i-1]);
        vi f(n+2);
        f[0]=1;
        for(int i=1,cur=0,sum=1;i<=n+1;++i){
            while(cur<lef[i])sum-=f[cur++],sum<0?sum+=Mod:1;
            if(!one[i])f[i]=sum;
            sum+=f[i],sum>=Mod?sum-=Mod:1;
        }
        return f[n+1];
    };
    int ans=1;
    for(int i=0;i<K;++i){
        vi a(m+1);
        for(int j=1;j<=m;++j)a[j]=(X[j]>>i)&1;
        int x=solve(a);
        (ans=1ll*ans*x)%=Mod;
    }
    printf("%lld\n",ans);
    return 0;
}