Code For C Code For D Code For F HDU - 6482 存在一个 *LGV(Lindström–Gessel–Viennot)*定理 对于一张无权的DAG图,给定NNN个起点和NNN个终点 设e(ai,bi)e(a_i,b_i)e(ai​,bi​)为点iii到点jjj的路径方案数,这NNN条不相交路径的方案数为 (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}⎝⎜⎜⎜⎛​e(a1​,b1​)e(a2​,b1​)⋮e(an​,b1​)​e(a1​,b2​)e(a2​,b2​)⋮e(an​,b2​)​⋯⋯⋱⋯​e(a1​,bn​)e(a2​,bn​)⋮e(an​,bn​)​⎠⎟⎟⎟⎞​ 这里我们有两个起点两个终点,代进去就就可以求出不相交的方案数了,然后用总路径数减去就好 至于如何求到点(i,j)(i,j)(i,j)的方案数,这里可以理解为,你需要走(i+j)(i+j)(i+j)步,在这(i+j)(i+j)(i+j)步中在何时往下走iii步的方案数,这样就转化为组合数问题,答案为Ci+jiC_{i+j}^iCi+ji​ HDU - 6483 先用ST表处理出区间的最大最小值 对于每个询问,mxmxmx表示该区间最大值,mimimi表示该区间最小值 然后可以将问题转化为询问区间内不同数的个数是否等于mx−mi+1mx - mi +1mx−mi+1 后面部分可以用莫队算法解决 HDU - 6485 枚举串sss的后缀,拿其与串ttt尺取 枚举串ttt的后缀,拿其与串sss尺取 所得的长度最大值,就是答案
Read More ~