IA 是一名会唱歌的女孩子。

IOI2018 就要来了，IA 决定给参赛选手们写一首歌，以表达美好的祝愿。这首歌一共有 (n) 个音符，第 (i) 个音符的音高为 (h_i)。IA 的音域是 (A)，她只能唱出 (1sim A) 中的正整数音高。因此 (1le h_ile A)。

在写歌之前，IA 需要确定下这首歌的结构，于是她写下了 (Q​) 条限制，其中第 (i​) 条为：编号在 (l_i​) 到 (r_i​) 之间的音符的最高音高为 (m_i​)。在确定了结构之后，她就可以开始写歌了。不过她还是想知道，一共有多少种可能的歌曲满足她的所有限制？她听说你还有 9 个月就要去 IOI 了，于是希望你帮她计算一下这个值。

(Qleq 500)。

题解

仓鼠《动态规划选讲》。

(max_{l≤i≤r}{A_i} = h)等价于(∀l ≤ i ≤ r, A_i ≤ h)且(∃l ≤ i ≤ r, A_i = h)。

求出每个点的上限(up_i)。可以发现，(∃l ≤ i ≤ r, A_i = h)的(i)只能由上限(up_i = h)的点来贡献

所以对于每个(h)的限制以及上限为(h)的点单独拿出来DP，满足每个限制区间中至少有一个点达到上限即可。

时间复杂度(O(Q^3))，可以利用前缀和优化到(O(Q^2))。

CO int N=1e3+10;
int m,n,A;
vector<int> num,val;
struct node {int l,r,m;} a[N];
int len[N],lim[N];
int t[N],l[N],f[N][N];

int solve(int x){
	int tot=0;
	for(int i=1;i<(int)num.size();++i)if(lim[i]==x){
		t[++tot]=i,l[tot]=0;
		for(int j=0;j<=tot;++j) f[tot][j]=0;
	}
	for(int i=1;i<=n;++i)if(a[i].m==x){
		if(!tot) return 0;
		int L=lower_bound(t+1,t+tot+1,a[i].l)-t;
		int R=lower_bound(t+1,t+tot+1,a[i].r)-t-1;
		l[R]=max(l[R],L);
	}
	f[0][0]=1;
	for(int i=1;i<=tot;++i){
		int v1=fpow(x,len[t[i]]),v2=fpow(x-1,len[t[i]]);
		for(int j=0;j<i;++j)if(f[i-1][j]){
			if(j>=l[i]) f[i][j]=add(f[i][j],mul(f[i-1][j],v2));
			f[i][i]=add(f[i][i],mul(f[i-1][j],add(v1,mod-v2)));
		}
	}
	int ans=0;
	for(int i=0;i<=tot;++i) ans=add(ans,f[tot][i]);
	return ans;
}
void real_main(){
	read(m),read(n),read(A);
	num={1,m+1},val.clear();
	for(int i=1;i<=n;++i){
		read(a[i].l),read(a[i].r),read(a[i].m);
		num.push_back(a[i].l),num.push_back(++a[i].r);
		val.push_back(a[i].m);
	}
	sort(num.begin(),num.end());
	num.erase(unique(num.begin(),num.end()),num.end());
	sort(val.begin(),val.end());
	val.erase(unique(val.begin(),val.end()),val.end());
	for(int i=1;i<(int)num.size();++i) len[i]=num[i]-num[i-1];
	for(int i=1;i<=n;++i){
		a[i].l=lower_bound(num.begin(),num.end(),a[i].l)-num.begin()+1;
		a[i].r=lower_bound(num.begin(),num.end(),a[i].r)-num.begin()+1;
	}
	for(int i=1;i<(int)num.size();++i) lim[i]=A+1;
	for(int i=1;i<=n;++i)
		for(int j=a[i].l;j<a[i].r;++j)
			lim[j]=min(lim[j],a[i].m);
	
	int ans=1;
	for(int i=1;i<=(int)val.size();++i){
		ans=mul(ans,solve(val[i-1]));
		if(ans==0) {puts("0"); return;}
	}
	for(int i=1;i<(int)num.size();++i)
		if(lim[i]==A+1) ans=mul(ans,fpow(A,len[i]));
	printf("%d
",ans);
}
int main(){
	for(int T=read<int>();T--;) real_main();
	return 0;
}

CF1327F AND Segments

You are given three integers (n, k, m) and (m) conditions ((l_1, r_1, x_1), (l_2, r_2, x_2), dots, (l_m, r_m, x_m)).

Calculate the number of distinct arrays (a), consisting of (n) integers such that:

• (0 le a_i < 2^k) for each (1 le i le n);

• bitwise AND of numbers (a[l_i] & a[l_i + 1] & dots & a[r_i] = x_i) for each (1 le i le m).

Two arrays (a) and (b) are considered different if there exists such a position (i) that (a_i eq b_i).

The number can be pretty large so print it modulo (998244353).

(1 le n le 5 cdot 10^5, 1 le k le 30, 0 le m le 5 cdot 10^5)

题解

显然每位独立，分开计算，用乘法原理合并。

如果(x_i=1)，那么毫无疑问区间内所有数都是(1)。

如果(x_i=0)，那么区间内至少有一个数为(0)。这个限制跟上一道题一模一样。

利用前缀和把DP优化到线性。时间复杂度(O(nlog n))。

CO int N=5e5+10;
struct node {int l,r,x;} a[N];
int V[N],L[N],S[N];
 
int solve(int n){
	fill(S+1,S+n+1,0),S[0]=1;
	int lim=-1;
	for(int i=1;i<=n;++i){
		if(!V[i]){
			int sum=add(S[i-1],mod-(lim>=0?S[lim]:0));
			lim=max(lim,L[i]-1);
			S[i]=add(S[i-1],sum);
		}
		else S[i]=S[i-1];
	}
	return add(S[n],mod-(lim>=0?S[lim]:0));
}
 
int fa[N];
 
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main(){
	int n=read<int>(),K=read<int>(),m=read<int>();
	for(int i=1;i<=m;++i) read(a[i].l),read(a[i].r),read(a[i].x);
	int ans=1;
	for(int c=0;c<K;++c){
		for(int i=1;i<=n;++i) fa[i]=i;
		fill(V+1,V+n+1,0);
		for(int i=1;i<=m;++i)if(a[i].x>>c&1)
			for(int p=find(a[i].r);p>=a[i].l;p=find(p))
				V[p]=1,fa[p]=p-1;
		fill(L+1,L+n+1,0);
		bool flag=0;
		for(int i=1;i<=m;++i)if(~a[i].x>>c&1){
			int p=find(a[i].r);
			if(!p) {flag=1;break;}
			L[p]=max(L[p],a[i].l);
		}
		if(flag) {ans=0;break;}
		ans=mul(ans,solve(n));
	}
	printf("%d
",ans);
	return 0;
}