Code For C
Code For D
Code For F

HDU - 6482

存在一个 *LGV(Lindström–Gessel–Viennot)*定理
对于一张无权的DAG图,给定NN个起点和NN个终点
e(ai,bi)e(a_i,b_i)为点ii到点jj的路径方案数,这NN条不相交路径的方案数为

(e(a1,b1)e(a1,b2)e(a1,bn)e(a2,b1)e(a2,b2)e(a2,bn)e(an,b1)e(an,b2)e(an,bn))\begin{pmatrix} e(a_1,b_1) & e(a_1,b_2) & \cdots & e(a_1,b_n) \\ e(a_2,b_1) & e(a_2,b_2) & \cdots & e(a_2,b_n) \\ \vdots & \vdots & \ddots & \vdots \\ e(a_n,b_1) & e(a_n,b_2) & \cdots & e(a_n,b_n) \end{pmatrix}

这里我们有两个起点两个终点,代进去就就可以求出不相交的方案数了,然后用总路径数减去就好
至于如何求到点(i,j)(i,j)的方案数,这里可以理解为,你需要走(i+j)(i+j)步,在这(i+j)(i+j)步中在何时往下走ii步的方案数,这样就转化为组合数问题,答案为Ci+jiC_{i+j}^i


HDU - 6483

先用ST表处理出区间的最大最小值
对于每个询问,mxmx表示该区间最大值,mimi表示该区间最小值
然后可以将问题转化为询问区间内不同数的个数是否等于mxmi+1mx - mi +1
后面部分可以用莫队算法解决


HDU - 6485

枚举串ss的后缀,拿其与串tt尺取
枚举串tt的后缀,拿其与串ss尺取
所得的长度最大值,就是答案