Codeforces1327 F. AND Segments（DP优化，按位）

You are given three integers 𝑛, 𝑘, 𝑚 and 𝑚 conditions (𝑙1,𝑟1,𝑥1),(𝑙2,𝑟2,𝑥2),…,(𝑙𝑚,𝑟𝑚,𝑥𝑚).

Calculate the number of distinct arrays 𝑎, consisting of 𝑛 integers such that:

0≤𝑎𝑖<2𝑘 for each 1≤𝑖≤𝑛; bitwise AND of numbers 𝑎[𝑙𝑖]&𝑎[𝑙𝑖+1]&…&𝑎[𝑟𝑖]=𝑥𝑖 for each 1≤𝑖≤𝑚. Two arrays 𝑎 and 𝑏 are considered different if there exists such a position 𝑖 that 𝑎𝑖≠𝑏𝑖.

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

Input The first line contains three integers 𝑛, 𝑘 and 𝑚 (1≤𝑛≤5⋅105, 1≤𝑘≤30, 0≤𝑚≤5⋅105) — the length of the array 𝑎, the value such that all numbers in 𝑎 should be smaller than 2𝑘 and the number of conditions, respectively.

Each of the next 𝑚 lines contains the description of a condition 𝑙𝑖, 𝑟𝑖 and 𝑥𝑖 (1≤𝑙𝑖≤𝑟𝑖≤𝑛, 0≤𝑥𝑖<2𝑘) — the borders of the condition segment and the required bitwise AND value on it.

Output Print a single integer — the number of distinct arrays 𝑎 that satisfy all the above conditions modulo 998244353.

Examples inputCopy 4 3 2 1 3 3 3 4 6 outputCopy 3 inputCopy 5 2 3 1 3 2 2 5 0 3 3 3 outputCopy 33 Note You can recall what is a bitwise AND operation here.

In the first example, the answer is the following arrays: [3,3,7,6], [3,7,7,6] and [7,3,7,6].

题意： 有m个限制条件，给一个区间，代表这个区间的数与起来结果为$x$。求有多少个这样的数组保证$0\le a[i]<2^k$满足这些限制条件。

思路： 参考博客

和二进制有关的题目一般都是按位考虑。 本题对于二进制第$i$位，假设区间$[l,r]$与起来的值第$i$位为1，那么这个区间所有数这个二进制位都为1。如果第$i$位为0，那么这个区间至少存在一个数该二进制位为0。

对于每个二进制位单独考虑。 定义$dp[i][j]$为考虑到第$i$个数，最后一个0出现的位置为$j$的方案数。

转移为$dp[i][j]=dp[i-1][j],1\le j\le i-1$ $dp[i][i]=\sum dp[i-1][j],1\le j\le i-1$

可以发现实际上只要维护第一维DP数组的前缀和，用这个前缀和算出$dp[i][i]$就好了。$dp[i][j],j<i$都可以直接继承之前的数。

所以可以省掉第一维，直接维护$dp[i]$代表最后一个0出现在第$i$位的方案数。

同时对于区间内至少有一个0的情况，则$dp[i]=\sum dp[j],pre[i]\le j\le i$ $pre[i]$代表$i$对应的这个限制区间的左边界，因为左边界以前的数是不存在$dp[j]，j<pre[i]$的，因为在$pre[i]$后面至少有一个0。

#include <cstdio> #include <algorithm> #include <cstring> #include <iostream> #include <vector> using namespace std; const int maxn = 5e5 + 7; const int mod = 998244353; typedef long long ll; ll dp[maxn]; int pre[maxn],cnt[maxn]; int n,k,m; struct Node { int l,r,x; }a[maxn]; ll solve(int pos) { for(int i = 0;i <= n;i++) { dp[i] = pre[i] = cnt[i] = 0; } for(int i = 1;i <= m;i++) { if(a[i].x & (1 << pos)) { cnt[a[i].l]++; cnt[a[i].r + 1]--; } else { pre[a[i].r] = max(pre[a[i].r],a[i].l); } } for(int i = 1;i <= n;i++) cnt[i] += cnt[i - 1]; ll sum = dp[0] = 1; int last = 0; for(int i = 1;i <= n;i++) { if(!cnt[i]) { dp[i] = sum; sum = sum * 2 % mod; } while(last < pre[i]) { sum = (sum - dp[last] + mod) % mod; last++; } } return sum; } int main() { scanf("%d%d%d",&n,&k,&m); for(int i = 1;i <= m;i++) { scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].x); } ll ans = 1; for(int i = 0;i < k;i++) { ans = ans * solve(i) % mod; } printf("%lld\n",ans); return 0; }