Atcoder agc056

發表於 更新於 分類於 ， Disqus： 文章字數： 4k 所需閱讀時間 ≈ 13 分鐘
B, DP,分治,前缀和,数学

题目

https://atcoder.jp/contests/agc056/tasks/agc056_b

一个长度为n的排列

对于q个查询构成的大小为q向量有多少种

其中每次查询排列[l..r] 中最大值的下标

n <= 300

查询不重复, 合法(l < r)

题解

考虑把数字从大到小放入排列的位置.

假设把N放在位置pos,那么有三类区间

  1. 包含pos的
  2. 完全在pos左侧
  3. 完全在pos右侧

那么显然对于所有查询区间包含pos的,返回都是pos

而对剩余的,如果把左侧位置的所有值保持相对顺序,右侧位置的所有值保持相对顺序, 然后调整值让左侧所有值大于右侧所有值, 对于输出的q维向量没有变化.(因为相对顺序不变,左侧和右侧内部,原来哪个位置大还是哪个大,且都在pos单侧互不影响), 因此不妨我们选定pos后如此调整

先不考虑重复

那么设计状态dp[i][j][pos] = 在[i..j]中, pos为最大值, 且属于[i..j]中某个完整区间的 方案数

那么注意到上面,当我们选定了pos, 就是把区间划分成[i..pos-1]pos[pos+1..j]

原题的答案变为 sum(dp[0][n-1][pos = 0..n-1])

其中注意到,我们在对于无效的pos结果为0, 例如 pos不属于[i..j]中任何一个完整区间, 其对应的情景是最大值不属于任何一个区间,那么 这个位置删掉都行 更不用考虑值了

那么上面的转移方程有

dp[0][n-1][pos] = sum(dp[0][pos-1][0..pos-1]) * sum(dp[pos+1][n-1][pos+1..n-1])

也就是 左侧 和 右侧分别独立计算.

而这个计算规则实际上和原问题是同一个问题. 因此可以看成是分治

dp[i][j][p] = sum(dp[i][p-1][i..p-1]) * sum(dp[p+1][j][p+1..j])

其中 sum为零时,记为1,属于空方案

引理: 分治中数值的大小无影响,只有输出有影响

因为隔离性,假设右侧不动,来考虑左侧的排列数值变化,但产出向量不变,对结果有什么影响.

假设左侧存在[1..2][3..4] 非重叠 或者 [1..2][2..3]重叠区间或其它任何状态, 那么可能不同的值,有相同的向量产生

一旦左侧的产出向量确定了, 注意到转移方程的剩余部分,一个是pos,那一定比左侧都大,而右侧根据它们的隔离性,比左侧都小,所以转移方程的任何剩余向量也不会受到影响.

所以, 转移方程只与单侧的向量产生相关, 与具体值无关

上面的东西,看上去搞个前缀和,再for(len)for(左端点i)for(最大值下标pos) 就搞完了

重复

基本的东西有了,下面是精确计算值

正如上面的例子[1..2][3..4]

如果是1234 输出是(2,4)

如果是3412 输出也是(2,4)

而对于dp来说,一个是按照 第4位 开始划分,一个是按照第2位开始划分的. 有重复的问题

同样,对于[1..2][2..3] 来说

如果312 和 213 也会重复.分别是第1位和第3位最大进行讨论的, 而它们的输出都是(1,3)

注意, 这里 132 和231 不会重复统计

一个办法是容斥(本文不会提到

另一个就是发现其数学性质

当在[i..j] 中 pos是最大值的下标 且属于其中某个完整区间时

如果[i..pos-1] 中的最大值 在idx, 且idx和pos 在[i..j] 中不属于任何同一个完整区间, 那么 让idx变为 [i..j]中的最大值, pos改为次大值,总输出向量不变

证明

因为前面假设过, value[pos] > 所有左侧值 > 所有右侧值,所以pos最大,idx次大

交换以后,value[idx] > value[pos] > 其它左侧值 > 所有右侧值

按情况讨论区间

  1. pos右侧的所有区间,因为包含的内容全在右侧值中,所以都不受影响
  2. 包含pos的所有区间, 原本输出pos, 因为不包括idx,现在pos次大,所以依然输出pos
  3. pos左侧所有区间, 只有idx变大了,但对于所有左侧区间来说,相对顺序都没有变化, 所以左侧的也都没有变

所以总的向量没有变

以上证明了,如果[i..pos-1]中的最大值和pos在[i..j]中不属于同一个完整区间,那么会被重复统计. 所以

dp[i][j][p] = sum(dp[i][p-1][i..p-1]) * sum(dp[p+1][j][p+1..j])

要改为

dp[i][j][p] = sum(dp[i][p-1][f(p)..p-1]) * sum(dp[p+1][j][p+1..j])

f(p) = 最小的 在[i..j]中和p属于同一个完整区间的

不漏从dp过程中已经保证了,上面我们只是提到了去重,而并不能说明所有重复都没有了.下面证明所有重复都没有了

即是证明 任何输出向量,只会被至多统计一次

不妨设某个 输出被统计了两次.

根据统计过程, 如果它在首次被不同的最大值下标统计了,那么

  1. 这两个下标属于同一个区间,和下标是最大值矛盾,一个区间只有一个下标是最大值
  2. 这两个下标不属于任何同一个区间,那么根据上面的变化, 只会统计在左侧为更大值

代码

基于 heno239 的代码 https://atcoder.jp/contests/agc056/submissions/27693073

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, n) for (ll i = a; i < n; i++)
#define per(i, a, n) for (ll i = n - 1; i >= a; i--)
constexpr ll mod = 998244353;
#define all(v) (v).begin(), (v).end()

struct modint {
  int n;
  modint() : n(0) { ; }
  modint(ll m) {
    if (m < 0 || mod <= m) {
      m %= mod;
      if (m < 0)
        m += mod;
    }
    n = m;
  }
  operator int() { return n; }
};
bool operator==(modint a, modint b) {
  return a.n == b.n;
}
modint operator+=(modint& a, modint b) {
  a.n += b.n;
  if (a.n >= mod)
    a.n -= mod;
  return a;
}
modint operator-=(modint& a, modint b) {
  a.n -= b.n;
  if (a.n < 0)
    a.n += mod;
  return a;
}
modint operator*=(modint& a, modint b) {
  a.n = ((ll)a.n * b.n) % mod;
  return a;
}
modint operator+(modint a, modint b) {
  return a += b;
}
modint operator-(modint a, modint b) {
  return a -= b;
}
modint operator*(modint a, modint b) {
  return a *= b;
}
modint operator^(modint a, ll n) {
  if (n == 0)
    return modint(1);
  modint res = (a * a) ^ (n / 2);
  if (n % 2)
    res = res * a;
  return res;
}

ll inv(ll a, ll p) {
  return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);
}
modint operator/(modint a, modint b) {
  return a * modint(inv(b, mod));
}
modint operator/=(modint& a, modint b) {
  a = a / b;
  return a;
}

vector<int> vle[305];       // [r pos] = {l pos...} 区间右端点到左端点
modint dp[305][305][305];   // [l][r][x] = [l..r-1] 最大的是x的方案数, 其中不论l取值多少,x与[l,r-1]至少属于[l,r-1]中的一个完整区间
modint rdp[305][305][305];  // rdp[l][r][i] =  dp[l][r][0..i-1] 的前缀和

// 默认 全false, 右端点在[l+1..r]之间，长度 <= r-l 的区间是否存在
bool exi[305][305];

int cl[305];  // 计算过程中[l..r-1] 中, cl[i] = 与i同属于完整区间属于[l..r-1]的 最左端点
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  rep(i, 0, m) {
    int l, r;
    scanf("%d %d", &l, &r);
    vle[r].push_back(l - 1);
  }
  // 同样右端点 左端点从小到大, 方便后面二分找满足条件的左端点
  rep(i, 0, n + 1) sort(all(vle[i]));
  rep(len, 1, n + 1) {    // 枚举 长度[1..n], 因为每次划分是 左右两个更短的范围
    rep(r, len, n + 1) {  // 右端点从小到大 [len..n]
      int l = r - len;    // 左侧端点 = 右端点-长度
      int nw = r; // 遍历过程中,当前属于[l..r-1]的完整区间的最小左端点
      per(j, l + 1, r + 1) {  // j（右端点）从大到小 [l+1,r] 范围内的每个右端点
        // 第一个大于或等于某个元素的位置, 二分查找
        int t = lower_bound(all(vle[j]), l) - vle[j].begin();
        if (t < vle[j].size()) {  // [nw,j] 区间小于等于 len
          nw = min(nw, vle[j][t]);
        }
        // 右端点 [j..r] 中的区间的最小左端点, 不存在的情况 r > j - 1
        cl[j - 1] = nw;
      }
      if (nw == r) {  // 没有任何有效区间
        exi[l][r] = false;
        continue;
      }
      exi[l][r] = true;  // 右端点在 [l+1 ..r], 长度小于等于 len 的区间 存在
      rep(x, l, r) {    // [l..r-1]
        if (x < cl[x])  // 不存在 [l,r] 之间的小区间 包含 坐标x
          continue;
        // [l..x-1]x[x+1..r-1]
        // 存在右端在 [l+1..x], 长度小于 x-l 的区间,
        // sl = sum{dp[l][x][cl[x]..x-1]}
        // 注意这里, 当[l..x-1]不存在时是1, 而[l..x-1]存在时,因为防止重复统计可能[cl[x]..x-1]是0
        modint sl = exi[l][x] ? rdp[l][x][x] - rdp[l][x][cl[x]] : (modint)1;
        // 存在右端在 [x+2..r], 长度小于 r-x-l 的区间,
        // sr = sum{dp[x+1][r][x+1..r-1]}
        // 而对于右侧 似乎可以直接判断前缀和是否非零,但实际上因为是取mod运算,可能为mod的倍数,所以还是需要一个exi的辅助数组
        modint sr =
            exi[x + 1][r] ? rdp[x + 1][r][r] - rdp[x + 1][r][x + 1] : (modint)1;
        dp[l][r][x] = sl * sr;  // [l,r-1]中 最大的下标为x, 方案数
        // 下面由此输出
        // printf("%d %lld %lld => %d %d\n",l,r,x,(int)sl,(int)sr);
      }
      rep(j, l, r) {
        // [l..r-1]
        // rdp[l][r][j] = dp[l][r][0..j-1] 前缀和
        rdp[l][r][j + 1] = rdp[l][r][j] + dp[l][r][j];
      }
    }
  }
  printf("%d", (int)rdp[0][n][n]); // [0,n-1] 最大下标[0..n-1]的方案数
  return 0;
}

例子

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
//
// [l          x-1]x[x+1          ]r
// x 是最大值
// dp[l][r][x] = 左边方案数 x 右边方案数, 其中右边的长度覆盖了x
//             = sum{dp[l][x][cl[x]..x-1]} * sum{dp[x+1][r][x+1..r-1]}
//             = x 是最大值，对左侧的影响当前 最近的是 cl[x]
//
//
// 012345678
//  xx
//   xxx
//     xxx
//      xx
//        xx
//
/*
9 5
2 3
3 5
5 7
6 7
8 9
*/
/*
l r x ==sl*sr
[l r) 左闭右开,所以 实际区间是[l..r-1]

len = 2
1 3 1 => 1 1
1 3 2 => 1 1

5 7 5 => 1 1
5 7 6 => 1 1

7 9 7 => 1 1
7 9 8 => 1 1

len = 3
0 3 1 => 1 1
0 3 2 => 1 1 (0不属于完整区间,所以没有 0 3 0

1 4 1 => 1 1
1 4 2 => 1 1 (虽然3和属于[2..4]的完整区间,但这里的区间是[1..3],3 不属于这之间的任何完整区间, 所以也没有 1,3,3

2 5 2 => 1 1
2 5 3 => 1 1
2 5 4 => 1 1

4 7 4 => 1 2 (首次包含关系 区间,一个[4..6]一个[5..6],右侧 = dp[5][7][5] + dp[5][7][6] = 1+1 = 2, 也就是[4..6] 最大值在4时,不影响右侧不包含它的区间,右侧有两种值
4 7 5 => 1 1
4 7 6 => 1 1

5 8 5 => 1 1
5 8 6 => 1 1

6 9 7 => 1 1
6 9 8 => 1 1

len = 4
0 4 1 => 1 1
0 4 2 => 1 1

1 5 1 => 1 3 (同 上面 4 7 4
1 5 2 => 1 1 (这个和下面两个都是 1 1, 但实际上有些不同, 下面两个的左边的1, 如果按照上面右侧的统计法,应该是 2 而不是1, 注意到上面算sl和sr是有区别的,一个是[cl[x]..x-1], 一个是[x+1..r], 如果一致应该是[l..x-1]而不是[cl[x]..x-1], 说面 左侧最大值, 一定要和x属于同一组,如果不同组, 让左侧更大,其它平移补位, 总输出不变. 所以下面两个都是1.
1 5 3 => 1 1
1 5 4 => 1 1 

2 6 2 => 1 1
2 6 3 => 1 1
2 6 4 => 1 1

3 7 4 => 1 2
3 7 5 => 1 1
3 7 6 => 1 1

4 8 4 => 1 2
4 8 5 => 1 1
4 8 6 => 1 1

5 9 5 => 1 2
5 9 6 => 1 2
5 9 7 => 0 1
5 9 8 => 0 1

len = 5
0 5 1 => 1 3
0 5 2 => 1 1
0 5 3 => 1 1
0 5 4 => 1 1
1 6 1 => 1 3
1 6 2 => 1 1
1 6 3 => 1 1
1 6 4 => 1 1
2 7 2 => 1 4
2 7 3 => 1 4
2 7 4 => 1 2
2 7 5 => 1 1
2 7 6 => 1 1
3 8 4 => 1 2
3 8 5 => 1 1
3 8 6 => 1 1
4 9 4 => 1 4
4 9 5 => 1 2
4 9 6 => 1 2
4 9 7 => 0 1
4 9 8 => 0 1

len = 6
0 6 1 => 1 3
0 6 2 => 1 1
0 6 3 => 1 1
0 6 4 => 1 1
1 7 1 => 1 12
1 7 2 => 1 4
1 7 3 => 1 4
1 7 4 => 1 2
1 7 5 => 1 1
1 7 6 => 1 1
2 8 2 => 1 4
2 8 3 => 1 4
2 8 4 => 1 2
2 8 5 => 1 1
2 8 6 => 1 1
3 9 4 => 1 4
3 9 5 => 1 2
3 9 6 => 1 2
3 9 7 => 0 1
3 9 8 => 0 1

len = 7
0 7 1 => 1 12
0 7 2 => 1 4
0 7 3 => 1 4
0 7 4 => 1 2
0 7 5 => 1 1
0 7 6 => 1 1
1 8 1 => 1 12
1 8 2 => 1 4
1 8 3 => 1 4
1 8 4 => 1 2
1 8 5 => 1 1
1 8 6 => 1 1
2 9 2 => 1 8
2 9 3 => 1 8
2 9 4 => 1 4
2 9 5 => 1 2
2 9 6 => 1 2
2 9 7 => 0 1
2 9 8 => 0 1

len = 8
0 8 1 => 1 12
0 8 2 => 1 4
0 8 3 => 1 4
0 8 4 => 1 2
0 8 5 => 1 1
0 8 6 => 1 1
1 9 1 => 1 24
1 9 2 => 1 8
1 9 3 => 1 8
1 9 4 => 1 4
1 9 5 => 1 2
1 9 6 => 1 2
1 9 7 => 0 1
1 9 8 => 0 1

len = 9
0 9 1 => 1 24
0 9 2 => 1 8
0 9 3 => 1 8
0 9 4 => 1 4
0 9 5 => 1 2
0 9 6 => 1 2
0 9 7 => 0 1
0 9 8 => 0 1
*/

改版

对于上面代码改了主要几个部分

把[l,r]改为左右都是闭区间了,不用考虑加减1的描述范围

把所有下标按照题目变成1-index而不是上面的0-index,因为这样也方便前缀和不用单独处理下标0

去掉了 大佬的modint, 假设没有modint的实现的情况下,直接加mod运算

https://atcoder.jp/contests/agc056/submissions/27743665

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, n) for (ll i = a; i < n; i++)
#define per(i, a, n) for (ll i = n - 1; i >= a; i--)
constexpr ll mod = 998244353;
#define all(v) (v).begin(), (v).end()

vector<int> vle[305];   // [r pos] = {l pos...} 区间右端点到左端点
ll dp[305][305][305];   // [l][r][x] = [l..r] 最大的是x的方案数, 其中不论l取值多少,x与[l,r]至少属于[l,r]中的一个完整区间
ll rdp[305][305][305];  // dp 前缀和
bool exi[305][305];     // 默认 全false, 在[l..r]之间 是否存在完整区间
int cl[305];            // 右端点 in [i..最右侧] = 区间的最小左端点
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  rep(i, 0, m) {
    int l, r;
    scanf("%d %d", &l, &r);
    vle[r].push_back(l);
  }
  rep(i, 1, n+1) sort(all(vle[i]));
  rep(len, 2, n+1) {              // 枚举 长度
    rep(r, len, n+1) {            // 右端点 从小到大
      int l = r - len + 1;        // 左侧端点 = 右端点 - 长度 +1
      int nw = r + 1;             // 左端点, 在[l..r] 中
      per(j, l, r + 1) {          // j（右端点）从大到小 [l,r] 范围内的每个右端点
        int t = lower_bound(all(vle[j]), l) - vle[j].begin();
        if (t < vle[j].size()) nw = min(nw, vle[j][t]);
        cl[j] = nw;
      }
      if (nw == r+1) {            // 没有任何有效区间
        exi[l][r] = false;
        continue;
      }
      exi[l][r] = true;           // 右端点在 [l+1 ..r], 长度小于等于 len 的区间 存在
      rep(x, l, r+1) {            // [l..x-1]x[x+1..r]
        if (x < cl[x]) continue;  // 不存在 [l,r] 之间的小区间 包含 坐标x
        ll sl = exi[l][x-1] ? rdp[l][x-1][x-1] - rdp[l][x-1][cl[x]-1] : 1;
        ll sr = exi[x+1][r] ? rdp[x+1][r][r] - rdp[x + 1][r][x] : 1;
        dp[l][r][x] = ((sl%mod) * (sr%mod))%mod;    // [l,r-1]中 最大的下标为x, 方案数
      }
      rep(j, l, r + 1) rdp[l][r][j] = (rdp[l][r][j-1] + dp[l][r][j])%mod;
    }
  }
  printf("%lld", (rdp[1][n][n]+mod)%mod); 
  return 0;
}

参考

官方题解 https://atcoder.jp/contests/agc056/editorial/3045