跳转至

251118 模拟赛

T1

发现用 \(1,2\) 把序列划分成 \(2\) 段，每段内单调递增，随后简单 dp 即可。

T2

有一个 \(n\times m\) 的矩阵，矩阵上下左右连通。你初始在矩阵左上角 \((1,1)\) 处，每次会移动到右上、右、右下三个格子中权值最大的那个格子上。维护两种操作：

  • 移动 \(k\) 步，并输出移动后的结果，本次询问会影响到之后的所有询问；
  • 单点修改矩阵权值；

\(n,m\le 2000,~q\le 5000\)

只要维护出从第一列每个格子走 \(m\) 步后会走回到哪个格子上，就可以简单跳基环树了。

修改一个点时，只会直接影响到它的左下，左，左上三个格子。暴力更新三个格子的目的地，然后从右往左递推哪些区间分别可以到达这些格子。每倒推一步区间只会变化 \(O(1)\)，因此可以做。

T3

咕咕咕

T4

称一个长度为 \(n\) 的正整数数列的权值为其最长上升区间的长度。

给定 \(n\) 个数 \(m_{1\sim n}\)，称一个整数序列合法当且仅当 \(\forall i,~a_i\in [1,m_i]\)。求所有合法序列的权值和，答案对 \(1004535809\) 取模。

\(n\le 500,~1\le m_i\le 10^9\)

先拆贡献，问题转化成对每个 \(k\) 统计出权值不小于 \(k\) 的区间数量。考虑容斥，钦定一个下标集合满足向后 \(k\) 个元素是上升的，赋予容斥系数 \((-1)^{|S|+1}\)。这样一个下标集合对应的上升区间可能会重叠，合并成大区间，这样一个大区间是整个被钦定上升的。因此考虑对每一个上升区间计数容斥系数之和，设 \(g_i\) 表示长度为 \(i\) 的上升区间的容斥系数之和，有转移：\(g_i=-\sum_{j=1}^{k-1}g_{i-j}\)。现在问题转化为预处理每个区间钦定上升的方案数。

发现直接做是没有前途的。考虑优化朴素的想法：枚举右端点，然后从右向左加入左端点，每次 \(O(V)\) 的更新 dp 数组。这种每次做后缀和的 dp 数组整个是一个多项式，考虑维护 \(\sum_{j=0}^{n}p_jx^{\overline{j}}\)，令其点值为 dp 数组的值。动态维护当前多项式值有效的区间 \(x\in [1,lim]\)，做完后缀和之后多项式变成：

\[ \begin{align*} \sum_{j=0}^{n}p_j\sum_{k=x+1}^{lim_{i+1}}k^{\overline{j}}&=\sum_{j=0}^{n}p_j\sum_{k=x+1}^{lim_{i+1}}\frac{1}{j+1}\big(k^{\overline{j+1}}-(k-1)^{\overline{j+1}}\big)\\ &=\sum_{j=0}^{n}\frac{\big(lim^{\overline{j+1}}-x^{\overline{j+1}}\big)}{j+1}p_j \end{align*} \]

这样可以 \(O(n)\) 移动左端点。

代码 
 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
#include<iostream>
#define int long long
using namespace std;
const int N = 510;
const int MOD = 1004535809;
const int INF = 0x3f3f3f3f;

inline void add(int &a, int b) { a += b; (a >= MOD) && (a -= MOD); }

int n, sum, ans;
int inv[N];
int a[N];

int w[N][N], p[N];
int pw[N];

int f[N], g[N];

signed main() {

    inv[1] = 1;
    for(int i = 2; i < N; i++) inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;

    cin >> n; sum = 1;
    for(int i = 1; i <= n; i++) cin >> a[i], sum = sum * a[i] % MOD;

    for(int r = 1; r <= n; r++) {
        for(int i = 0; i <= n + 5; i++) p[i] = 0;
        p[0] = 1; int lim = a[r];
        for(int i = r; i >= 1; i--) {
            if(lim < 0) break;
            pw[0] = 1;
            for(int j = 1; j <= n + 2; j++) pw[j] = pw[j - 1] * (lim + j - 1) % MOD;
            int s0 = 0;
            for(int j = n + 2; j >= 0; j--) {
                p[j + 1] = (MOD - p[j] * inv[j + 1] % MOD) % MOD;
                add(s0, p[j] * inv[j + 1] % MOD * pw[j + 1] % MOD);
            }
            p[0] = s0;
            add(w[r][i], p[0]);
            lim = min(lim - 1, a[i - 1]);
        }
    }

    add(ans, sum);
    for(int k = 2; k <= n; k++) {
        for(int i = 0; i <= n + 2; i++) f[i] = g[i] = 0;
        g[1] = 1;
        for(int i = k; i <= n; i++) {
            for(int j = 1; j <= k - 1; j++) add(g[i], MOD - g[i - j]);
        }
        f[0] = 1;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= i; j++) add(f[i], f[i - j] * w[i][i - j + 1] % MOD * g[j] % MOD);
        }
        add(ans, (sum - f[n] + MOD) % MOD);
    }

    cout << ans << '\n';

    return 0;
}