CF1327F. AND Segments

发表于 | 阅读数

让你求一个序列$a[l_i]\&a[l_i+1]….a[r_i]=x$的方案数。$0\leq a^i<2^k$
二进制位之间独立,按位讨论。若$(l,r,x),x=1$则里面都是$1$。若$(l,r,x),x=1$，至少出现是$1$。

拿样例$2$的第$1$位解释

$5\ 2\ 3$

$1\ 3\ 2$

$2\ 5\ 0$

$3\ 3\ 3$

分解就是$??1??$,$(1,3)和(2,5)$至少有一个$0$。

设$dp[i][j]$为前第$i$数，最前面的$0$在第$j$位的填法。

若搜到出现边界$r$,

  • $[r,l_x],[r,l_y]$取$min(l_x,l_y)$
  • 若这一位填$0$,$dp[i][i]=\sum dp[i-1][j]$
  • 若这一位填$1$,需要$(l,r)$之间有$0$。$dp[i][j]=\sum_l^{r-1} dp[i-1][j]$
  • 发现了$i-1$这一唯独不需要。$\sum dp[j]-\sum_0^{l-1}dp[j]=\sum_l^{r-1} dp[j]$

假设$r_x>r_y$,若$l_x<l_y$，则之前的方案已经保证了$[l_x,r_x]$不需要重新计算，所以只需记录下$\sum dp$，每次需要减去的指针一定不会向后移动。

代码 
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
    using namespace std;
typedef long long ll;
const int N = 5e5 + 10;
const int mod = 998244353;
int l[N], r[N], x[N];
int ans = 1;
int n, s[N], mx[N];
int m, k;
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= k; i++)
        scanf("%d%d%d", l + i, r + i, x + i);

    for (int i = 0; i < m; i++)
    {

        for (int j = 1; j <= n; j++)
            s[j] = 0, mx[j] = 0;
        for (int j = 1; j <= k; j++)
        {

            if (x[j] & (1 << i))
                s[l[j]]++, s[r[j] + 1]--;
            else
                mx[r[j]] = max(mx[r[j]], l[j]);
        }
        for (int j = 1; j <= n; j++)
            s[j] += s[j - 1];
        int dp[N];
        dp[0] = 1;
        int t = 0;
        ll dps = 1;

        for (int j = 1; j <= n; j++)
        {
            if (s[j] > 0)
            {
                dp[j] = 0;
            }
            else
            {
                dp[j] = dps;
            }
            while (t < mx[j])
            {
                dps = (dps + mod - dp[t]) % mod;
                t++;
            }
            dps += dp[j];
            dps %= mod;
        }
        //cout << dps << endl;
        ans = 1ll * dps * ans % mod;
    }
    printf("%d\n", ans);
}