有点想做一些多校的题目练手。发现有一场是杜教出的？来体验一下被虐的快感～～

Expression

给定一个表达式，运算符包括加减乘。每次可以选择两个数执行运算。求所有运算顺序得到的结果之和。答案对$10 ^ 9 + 7$取模。

$2 \le n \le 100, 0 \le a_i \le 10 ^ 9$

比较明显的区间DP。设$dp(i,j)$为第$i$到$j$个数所有运算顺序结果的和，则有

$$dp(i,j) = \sum_{k = i} ^ {j-1} {{j - i - 1 \choose k - i} f(i,j,k)}$$

其中$f(i,j,k)$是与$k$位置后的运算符有关的转移函数。

上述式子中组合数的意义是，我们将左区间和右区间并起来时，考虑到左右区间各选择一个结果$p,q$，产生新的结果方式有${j - i - 1 \choose k - i}$种。

考虑加法运算，相当于在左右区间分别选择一个结果相加，即$\sum_{p \in L} \sum_{q \in R} {p + q}$。那么左区间的某一结果$p$对于答案的贡献是$(k - i)!p$，同理右区间的某一结果$q$对于答案的贡献是$(j-k-1)!q$，故此时

$$f(i,j,k) = (k-i)!dp(i,k) + (j-k-1)!dp(k+1,j)$$

减法运算类似。

再考虑乘法运算，相当于在左区间和右区间分别选择一个结果相乘，即$\sum_{p \in L} \sum_{q \in R} {pq}$。我们可以化简化一下式子，$(\sum_{p \in L} {p})(\sum_{q \in R} {q}) = dp(i,k) dp(k+1,j)$。故此时

$$f(i,j,k) = dp(i,k) dp(k+1,j)$$

时间复杂度$O(n ^ 3)$。

Hack it!

定义字符串$s$的哈希函数$f(s) = \sum_{i=0} ^ {n-1} {w(s_i) base ^ i} \mod r$。构造两个等长的合法括号序列$A,B$，长度$\le 10 ^ 4$，满足$f(A) = f(B)$。其中$w('(') = p,w(')') = q$。保证数据随机。

$1 \le p,q,r,base \le 10 ^ {18}$

GCD Tree

有一个带权完全图，点编号为$1$到$n$。边$(u,v)$的权值为$\gcd(u,v)$。求图的最大生成树。

测试数据约$10 ^ 5$组。$1 \le n \le 10 ^ 5$

本来以为这题有一些结论的，没想到是这么暴力的方法～

考虑按边权从大到小枚举边，设现在枚举到$d$，考虑边$(u,v)$，且$u,v \gt d$，那么这条边可以用$(d,u)$和$(d,v)$两条边等效替代。于是我们只要考虑$d$和$d$的倍数连边的情况。换言之，我们只需考虑$v$是$u$的倍数的边$(u,v)$。

根据调和级数，有$O(n\log n)$条这样的边。用LCT动态维护最大生成树即可。维护时记录一下答案，即可$O(1)$回答询问。

时间复杂度$O(n \log ^ 2 n)$。

Too Simple

有$m$组函数$f_1,f_2,...,f_m$。定义域和值域均为$[1,n]$的整数。现给定部分函数，求有多少种合法的函数序列，满足对于$1 \le i \le n$，$f_1(f_2(...f_m(i))) = i$。答案对$10 ^ 9 + 7$取模。

$1 \le n,m \le 100$

考虑这些函数，必定都是一对一的，而不会是多对一的。因为若有函数多对一，那么多个值就会映射到同一个值，最后不可能满足条件。所以这些函数实际上都是置换。

接下来我们分情况讨论。

如果所有函数都已经给定，我们只需将它们代入验证即可。

如果存在函数是未知的，我们只要确定$m-1$个函数，就能唯一地确定余下的一个函数。所以我们可以自由地决策$cnt-1$个函数，其中$cnt$是未知的函数数量。故答案为$(n!)^{cnt-1}$。

Arithmetic Sequence

定义序列$s$是$(d_1,d_2)$等差的，当且仅当存在$i$满足，对任意$1 \le j \lt i$有$s_{j+1} = s_j + d_1$，对任意$i \le j \lt n$有$s_{j+1} = s_j + d_2$。

现给定序列$a$，求有多少区间$[l,r]$时$(d_1,d_2)$等差的。

$1 \le n \le 10 ^ 5, |a_i| \le 10 ^ 9, |d_1|,|d_2| \le 1000$

不妨分成两种情况讨论。

$d_1 = d_2$时，我们就是要找序列中有多少个公差为$d_1$的等差数列。求出所有极长等差数列统计一下答案。

$d_1 \neq d_2$时，对于每个位置$i$，处理一下左边和右边分别可以延伸到的位置，乘法原理统计答案。

时间复杂度$O(n)$。

Persistent Link/cut Tree

有$m+1$棵树。$T_0$仅有一个点$0$。$T_i$的构造方式如下：选择两棵树$T_{a_i},T_{b_i}$，在$T_{a_i}$中的$c_i$和$T_{b_i}$中的$d_i$连一条长度为$l_i$的边。若$T_{a_i}$有$k$个点，将$T_{b_i}$中所有点的编号加上$k$。

对于任意$i$，若$T_i$有$n$个点，求$\sum_{i=0} ^ {n-1} \sum_{j=i+1} ^ {n-1} {dist(i,j)}$。答案对$10 ^ 9 + 7$取模。

测试数据约$100$组。$1 \le m \le 60,0 \le a_i,b_i \lt i,0 \le l_i \le 10 ^ 9$。

Travelling Salesman Problem

有一个$n \times m$的网格。每个格子里有一个非负整数。现要从$(1,1)$走到$(n,m)$，每次可以从一个格子走到一个相邻的格子，同一个格子不能经过两次。最大化经过格子的权值之和。输出路径。

$1 \le n,m \le 100, nm \ge 2, 0 \le a_{ij} \le 10 ^ 4$

$n$和$m$若有一个是奇数，我们就可以遍历整个棋盘。因为权值非负，直接遍历棋盘即可。

接着$n$和$m$均为偶数的情况我就不会啦～～

[UPD] 杜教的题太神啦。我们考虑棋盘的黑白染色，不妨设$(1,1)$是黑色，故$(n,m)$也是黑色。考虑一条路径，因为路径上的颜色一定时交替的，所以黑色恰好比白色多一格。又因为棋盘上黑白格子数目相等，所以一定有一个白格没有经过。于是我们不经过权值最小的白格就好了。构造比较显然，但是考虑的情况较多，FST好题。

时间复杂度$O(nm)$。

Goldbach's Conjecture

令$d(x)$为$x$所有约数的和。我们称$x$是一个好数，当且仅当$[1,d(x)]$中的所有整数均可以表示为$x$的某些约数之和。

询问一个偶数$p$是否可以表示成两个好数之和。输出方案。

测试数据约$40000$组。$1 \le p \le 10 ^ {18}$

Sometimes Naive

有$n$个点的树。点$i$的权值为$w_i$。现要求支持两种操作：

1 u w： 将点$u$的权值修改为$w$。

2 u v：求$\sum_{i=1} ^ {n} \sum_{j=1} ^ {n} {f(i,j)}$。若路径$(u,v)$与路径$(i,j)$有交点，$f(i,j) = w_i w_j$，否则$f(i,j) = 0$。答案对$10 ^ 9 + 7$取模。

$1 \le n,m \le 10 ^ 5, 0 \le w_i \le 10 ^ 9, 0 \le w \le 10 ^ 9$