NOIP 模拟赛 #16

A

link

设 \(f[i, j, x, y, w]\) 表示走到了 \((i, j)\) 且之前已经买了 \(x\) 张向下走的票和 \(y\) 张向右走的票，总花费为 \(w\) 的方案数。

大力 dp 即可。

B

link

注意 \(\prod x = \min x\) 的限制比较严格，很容易想到 \(\min x = 0\)，发现除此之外只有一种可能： \(\{1, 1\}\)。

考虑 \(\text{mex}\) 过大时一定是无用的，进而发现 \(\text{mex} \le 4\)。

分类讨论即可。

C

一张无向图有 \(n\) 个点，每个点有权值 \(a_u\)，初始没有边，并给出两个常数 \(u, v\)。支持每次加入一条边，删掉一条边，单点修改 \(a\)，给定 \(x\) 查询 \(\left (\sum\limits_{i = 1} ^ k \prod\limits_{u\in S_i} (a_u + x) \right) \bmod u^v\)，其中 \(S_1, S_2, \dots, S_k\) 为图中的所有连通块。

\(1\le n, q\le 10^5,\ 1\le u\le 10, \ 1\le v\le 4\)

首先边和点权的修改都可以线段树分治。

考虑如何高效处理 \(\bmod u^v\)，设 \(x = x_1u + x_0\)，式子可以变为 \(\sum\limits_{i = 1} ^ k \prod\limits_{u\in S_i} ((a_u + x_0) + x_1u)\)。

把 \((a_u + x_0)\) 和 \(x_1u\) 两个项拆出来，注意到若同时乘了 \(\ge v\) 个 \(x_1u\)，那么贡献为 \(0\)。

所以对于一个连通块，设 \(f_{c,i}\) 表示选了 \(i\) 个 \(x_1u\)，并且 \(x_0 = c\) 的其他数的连乘积之和。

合并两个连通块可以背包，在一个连通块中加入一个数可以直接更新。