有的时候一言难尽

A

求满足\(1 \leq a_{i, j} \leq K\)，并且\(a_{i, j} \leq a_{i, j+1}\)，\(a_{i, j} \leq a_{i+1,j}\)，\(a_{R, C}=V\)的\(N*M\)的大小的矩阵的数量

其中\(1 \leq R \leq N, 1 \leq C \leq M\)

注意到值为\(i-1\)和值为\(i\)的部分有一条分界线，一共有\(K\)条，把这些分界线稍微作移动，他们就等价于不相交的路径，我们很容易通过这些分界线来还原出原来的取值

对于\(a_{R, C}=V\)，就是\((R, C)\)这个点上方有\(V-1\)条分界线，在LGV引理中，我们可以把所有满足在\((R, C)\)上方的分界线的权值记为\(x\)然后算行列式，然后考虑\(V-1\)次的系数即可

直接计算\(x\)可能较为复杂，我们可以考虑对\(x\)进行赋值之后进行插值

D

给定\(\{A_n\}, \{B_n\}, \{C_n\}\)，对\(k = 1, 2, ..., N\)，求 \[ Ans_k = \sum_{1 \leq i \leq N} (C_i \times \prod_{1 \leq j \leq k}(A_i + B_j)) \]

看不懂题解，题解提到了一个Tellegen’s Principle，这个原则说linear straight-line program的转置和原问题有相同的复杂度，但是这个principle没有给出通用的构造，还是要对具体问题进行具体地设计，题解论文里提了这个题的转置转置后的做法，但感觉不够直观，我们就对这个题具体给出一个直观分析

设\(S_j = \sum_{i} C_i A_i^j\)，\(f_k(x) = \prod_{1 \leq j \leq k} (x + B_j)\)

那么，我们有\(Ans_k = \sum_{i=0}^k f_k(x)[x^i] S_i\)，其中\(\{S_n\}\)不难通过FFT计算

接下来，我们考虑分治，具体的，对区间\([l,r]\)分析

区间\([l, mid]\)中的\(B\)对于\([l, mid]\)中\(Ans\)的影响可以递归考虑，我们只需要考虑\([l, mid]\)中的\(B\)对\([mid+1, r]\)的\(Ans\)的影响，注意到我们只需要考虑\([mid+1, r]\)中的\(Ans\)中含且仅含\([l, mid]\)中的\(B\)的项，而这可以通过一个卷积来计算

总的复杂度就是\(O(n \log^2 n)\)