CF1327F 题解

CF1327F 题解

$\text{Description}$

给定 $n,k,m$ 及 $m$ 个限制三元组形如 $(l_i,r_i,x_i)$。

计算满足下列条件且长度为 $n$ 的序列 $a$ 数量:

  • $\forall i\in [1,n],a_i\in[0,2^k-1]$。
  • $\forall i\in[1,m],\bigoplus\limits_{j=l_i}^{r_i}a_j=x_i$,其中 $\bigoplus$ 表示将这些数按位与。

$n,m\le 5\times 10^5,k\le 30$。

$\text{Solution}$

首先由于位运算对于每个二进制位都是独立的,所以我们可以按位考虑,那么问题转换为 01 问题。

考虑一个简单的 DP,令 $l(i)$ 表示只考虑前 $i$ 个数,最后一个 $0$ 可以填的最靠前的位置,这个东西实际上是所有限制三元组中满足 $x_j=0$ 且 $r_j\le i$ 的东西中最大的 $l_j$,因为如果不是最大的 $l_j$,就意味着有些限制三元组的区间内都是 $1$,与条件不符了。再令 $f(i,j)$ 表示前 $i$ 个数填好且最后一个 $0$ 的位置在 $j$ 的方案数,我们有以下转移:

  • $j< l(i)$,此时不满足条件,则 $f(i,j)=0$。
  • $j\in[l(i),i-1]$,此时只能填 $1$,故有 $f(i,j)=f(i-1,j)$。
  • $j=i$,此时有转移:$f(i,i)=[\forall t\in [1,m],i\notin[l_t,r_t]]\sum\limits_{k=l(i-1)}^{i-1}f(i-1,k)$

复杂度太高,无法接受。但是我们发现第二种转移情况会使得 $\forall j\in[l(i),i-1]$ 都有 $f(i,j)=f(j,j)$,所以第三种转移的 sigma 又可以写成:$\sum\limits_{k=l(i-1)}^{i-1}f(k,k)$。

然后使用前缀和优化即可。

复杂度 $O(k(n+m))$。

$\text{Code}$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
#define REG register
using namespace std;

const int Mod=998244353,Maxn=500005;

inline void read(int& x){
static char c;
while(!isdigit(c=getchar()));x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}

inline int Max(int a,int b){return a>b?a:b;}
inline int Add(int a,int b){return (a+=b)>Mod?a-Mod:a;}
inline int Del(int a,int b){return (a-=b)<0?a+Mod:a;}

int n,k,m;

struct Opt{int l,r,x;}opt[Maxn];

int dp[Maxn],del[Maxn],l[Maxn],pi,s,pos;

inline int Solve(int nk){
s=1,pos=0,memset(del,0,sizeof del),memset(l,0,sizeof l),memset(dp,0,sizeof dp);
for(REG int i=1;i<=m;++i)
if(opt[i].x&(1<<nk)) ++del[opt[i].l],--del[opt[i].r+1];
else l[opt[i].r]=Max(l[opt[i].r],opt[i].l);
for(REG int i=1;i<=n+1;++i) l[i]=Max(l[i],l[i-1]),del[i]+=del[i-1];
dp[0]=1;
for(REG int i=1;i<=n+1;++i){
if(del[i]){dp[i]=0;continue;}
while(pos<l[i-1]) s=Del(s,dp[pos++]);
dp[i]=s,s=Add(s,dp[i]);
}
return dp[n+1];
}

inline void Work(){
read(n),read(k),read(m);
for(REG int i=1;i<=m;++i) read(opt[i].l),read(opt[i].r),read(opt[i].x);
int Ans=1;
for(REG int i=0;i<k;++i) Ans=1ll*Ans*Solve(i)%Mod;
printf("%d\n",Ans);
getchar(),getchar();
}

int main(){Work();}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×