CF1327F AND Segments

简单的 DP。

根据 $\text{AND}$ 位运算的的性质，我们显然可以拆成每一位单独考虑，最后乘起来即可。转化为，有现在一条线段上已经填了若干连续的 $1$，现有若干限制 $[l_i,r_i]$ 中至少有一个 $0$，问满足限制的方案个数。

这种问题很容易想到容斥，但是很难做到一个比较优秀的复杂度。考虑直接 DP，设 $f(i,j)$ 表示填到第 $i$ 个位置，上一个 $0$ 是在 $j$ 位置。转移时从左到右枚举 $r_i$，但是直接做单次 DP 是 $\mathcal O(n^2)$ 的。考虑优化一下，我们发现每次转移过程中发生变化的只有 $\displaystyle f(i,i)=\sum_{x=l_{i-1}}^{i-1}f(i-1,x)=\sum_{x=0}^{i-1}f(i-1,x)$，即在 $i$ 这一位填 $0$。实际上 有值的位置是单增的，于是转移时维护左端点，以及总和即可。时间复杂度 $\mathcal O(k(n+m))$。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int N=5e5+10,mod=998244353;
template<class T>
inline void read(T &x)
{
    x=0;int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,k,m;
int l[N],r[N],x[N];
int cnt[N],f[N];
int q[N];
inline int adj(int x){return x>=mod?x-mod:x;}
inline int solve(int bit)
{
    memset(cnt,0,sizeof(cnt));
    memset(q,0,sizeof(q));
    memset(f,0,sizeof(f));
    for(int i=1;i<=m;i++)
    {
        if(x[i]>>bit&1)cnt[l[i]]++,cnt[r[i]+1]--;
        else q[r[i]+1]=max(q[r[i]+1],l[i]);
    }
    int l=0,sum=f[0]=1;
    for(int i=1;i<=n+1;i++)
    {   
        cnt[i]+=cnt[i-1];
        while(l<q[i])sum=adj(sum-f[l]+mod),f[l]=0,l++;
        f[i]=cnt[i]?0:sum;
        sum=adj(sum+f[i]);
    }
    return f[n+1];
}
int main()
{
    read(n,k,m);
    for(int i=1;i<=m;i++)read(l[i],r[i],x[i]);
    int ans=1;
    for(int i=0;i<k;i++)ans=1ll*ans*solve(i)%mod;
    printf("%d\n",ans);
    return 0;
}