100+22+90=212。前两道题不错，但T3 没什么意义。

围观刘老爷超强 T1 解法。

【题目简介】

我本可以容忍黑暗，如果我不曾见过太阳。

考试内容略有超纲，不超纲的都给了非常多的部分分。

注意常数优化与超光速快速读入的运用

【题目信息】

时间限制：(2.5s)

空间限制：(512MB)

(O2:) 没有

【题目背景】

(ChiTongZ) 实在想不出背景，便开始玩猜数游戏，为了不让他鸽掉出题，请帮他完成猜数游戏。

【题目描述】

给定一个序列 ({a_n}) ，每一次你需要指定一个区间 ([l,r]) ，并查询这个区间的数的和的奇偶性，花费的代价 (c_{ij}) ，求得出所有的 (a_i) 的值的最小花费。

保证 (a_iin {0,1}) 。

【输入格式】

第一行为 (n) 。

第二行起为一个矩阵，其中第 (i) 行有 (n-i+1) 个数，

其中第 (i) 行表示 (c_{ii},c_{i(i+1)},c_{i(i+2)},cdots ,c_{in})

【输出格式】

一行一个数表示最小花费。

【样例输入】

(game.in)

(3\8 4 2\8 1\9)

【样例输出】

(game.out)

7

【数据范围 (/) 提示】

对 (5\%) 的数据满足 (nleq 300)

对 (100\%) 的数据

(1leq c_{ij} leq 10^{9})

(1leq nleq 3 imes 10^3)

---

【题目信息】

时间限制：(3s)

空间限制：(512MB)

(O2:) 没有

【题目背景】

(ChiTongZ) 拿着某一道奇奇怪怪的题目请教大佬，大佬给了 (ChiTongZ) 一道更加奇奇怪怪的题目，(ChiTongZ) 测了 (50) 次都没有 (AC) ，为了体现 (OIer) 互帮互助的精神，你需要解决这一道题。

【题目描述】

大佬发现 (ChiTongZ) 的提交记录构成了一个奇奇怪怪的矩阵，全是 (WA) ，但是相邻的格子的分数值得研究，假设矩阵有一个奇怪值，定义为

(sumlimits_{i=1}^nsumlimits_{j=1}^mnum_{ij}*A_{ij}^2)

其中 (n) 表示矩阵的行数，(m) 表示矩阵的列数，(num_{ij}) 表示第 (i) 行第 (j) 个元素上下左右四个方向上有多少个元素与 (A_{ij}) 的值不同，当然 (A_{ij}) 就表示矩阵第 (i) 行第 (j) 个元素了。

保证矩阵有 (c) 种颜色，并且 (A_{ij}in[1,c])

告诉你矩阵的行数 (n) ，列数 (m) ，还有每一种颜色的格子数量 (p_i) ，请求出矩阵奇怪值尽量小的一种方案，至于要多小，见提示。

【输入格式】

第一行三个整数 (n,m,c) 表示矩阵行数，矩阵列数，颜色的种类数。

第二行 (c) 个数字，第 (i) 个数 (p_i) 表示颜色为 (i) 的格子的数量。

保证 (sumlimits_{i=1}^cp_i=n imes m)

【输出格式】

第一行为你的矩阵的奇怪值。

第二行起的连续 (n) 行描述这个矩阵，第 (i) 行 (j) 个元素表示 (A_{ij}) 。

【样例输入】

(matrix.in)

(5 5 5\4 2 1 7 11)

【样例输出】

(matrix.out)

(290\5 5 5 4 4\5 5 1 4 4\5 5 1 4 4\5 5 1 1 4\5 5 2 2 3)

【数据范围 (/) 提示】

对于 (100\%) 的数据，满足 (1leq n,m,cleq 10, 1leq A_{ij}leq c) 。

---

每一个测试点的分值给法如下

对于每一个测试点，有一个阈值 (w) ，设 (p) 表示你的程序的答案(如果合法)。

若 (pleq 1.1w) 分值为 (5) 分。

若 (1.1w<pleq 1.4w) 分值为 (3) 分。

若 (1.4w<pleq 2.0w) 分值为 (1) 分。

此外情况为 (0) 分，不合法的答案也为 (0) 分。

不要尝试输出答案为 (0) ，(SPJ) 会检测你的结果与你的矩阵是否相符。

不同的矩阵构造方式可能会有相同的分数，由 (SPJ) 给出结果。

---

【题目信息】

时间限制：(1s-1.5s)

空间限制：(512MB)

(O2:) 没有

【题目背景】

(ChiTongZ) 向 (LDJ) 借了一棵树，为了更好的了解这一棵树，他想问你一个问题。

【题目描述】

每一个节点有两个权值 (c_i,b_i) ，定义一个节点 (u) 的可爱度如下：

从节点 (u) 的所有的子节点(包括 (u) )当中选择一部分点，并且 (u) 可以选择可以不选择，将其权值 (c_i) 相乘，并对 (M) 取模，可以得到一个正整数 (k)，要求 (b_uequiv k (mod M)) 的取节点总方案数为 (u) 的可爱度。

为了更好的了解这一棵树，(ChiTongZ) 想要知道所有的节点的可爱度。

由于不想写高精度，答案请对 (998244353) 取一取模。

不选节点视乘积为 (1) 。

【输入格式】

第一行两个正整数 (n,M) ，表示节点的个数,模数。

第二行起的 (n-1) 行，每行两个整数 (x,y) ，表示点 (x) 与点 (y) 有边直接相连。

接下来的一行有 (n) 个整数，表示每一个节点的权值 (c_i) 。

接下来的一行有 (n) 个整数，表示每一个节点的权值 (b_i) 。

【输出格式】

输出一行一共 (n) 个整数，表示每一个节点的可爱度。

【样例输入】

(tree.in)

(5 13\1 2\2 4\2 5\1 3\5 1 4 2 7\2 1 3 2 2)

【样例输出】

(tree.out)

(4 4 0 1 0)

【数据范围 (/) 提示】

对于 (90\%) 的数据，满足 (n,mleq 100)，测试点时限 (1s)

对于另外 (10\%) 的数据，满足测试点时限 (1.5s)

对于 (100\%) 的数据，满足 (nleq 3000, Mleq 10000,1leq c_i,b_i<M) 并且 (M) 为质数，保证 (b_i,c_i) 不为 (M) 的倍数。

T1

部分分做法

或许可以搜索？

满分做法

考虑每一次询问 ([i,j]) 实际上是得到了 (sum_{i-1}) 与 (sum_j) 的对应关系，就是知道其中一个，另外一个就知道了，另外这个关系可以转移，就是对于 (i<j<k) 知道了 (sum_{i}) 与 (sum_k) 的关系，知道了 (sum_j) 与 (sum_k) 的关系，就知道了 (sum_i) 与 (sum_j) 的关系，所以是不会存在环的，于是就可以使用最小生成树解决。

T2

部分分做法

贪心，动态规划等等都可以试一试。

满分做法

考虑搜索，但是时间复杂度太高，所以模拟退火优化，卡一卡。

每次找两个格子，交换位置，答案更优就保留，否则按照某个随随机次数增多而减小的概率保留答案。

这道题是 这道题 的弱化版，卡参数不那么严重。

T3

部分分做法

考虑直接 (DP) ，明显设 (f[i][j]) 表示第 (i) 个节点及子节点当中选出乘积为 (j) 的方案数，所以直接转移就可以了。

满分做法

多项式乘法可以解决剩下的 (10) 分。

将状态转移方程列出来之后发现是((v) 为 (u) 的子节点)

(f[u][k]=sumlimits_{i imes j=k}f[u][i] imes f[v][j])

左边是新的 (f) ，右边是旧的 (f) ，运算时不能覆盖。

这个式子有一点多项式的样子，但是运算符是乘法，不能够直接 (NTT/FFT) ，所以考虑转化一下。

由套路可得，在 (M) 为质数时，可以直接求出模 (M) 的原根 (g) ，并把每一个数 (x) 表示为 (log_gx) ，于是状态转移就变成了

(f[u][log_gk]=sumlimits_{log_gi+log_gj=log_gk}f[u][log_gi] imes f[v][log_gj])

然后就可以 (NTT/FFT) 快速计算了。