QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB
[+2]
Statistics

题解 by @ezoilearner,你可以通过以下联系方式联系作者:

  • QQ: 2939863838

题意:我们称三运组 (p,q,s) 合法当且仅当村存在矩阵 a2×n

0 p,q 是个 长为 n 的排列,s 是一个长为 n01 字符串。

1 12n 的整数在里面恰好出现一次;

2 i,j,[a1,i<a1,j]=[pi<pj] .

3 i,j,[a2,i<a2,j]=[qi<qj] .

4 i,a1,i<a2,i=[si=0] .

f(p,q) 定义为满足条件的 s 的个数。

给定 p ,给定 q 的若干位置,求对于所有满足条件的 q ,f(p,q) 的和。

n100

题解:可以认为 {p}=1,2,,N .

这样情况下,不能存在 i>j,qi<qj,si=0,sj=1 ,其实这也是充分条件。

进而考虑 f(p,q) 的计算,其实就是 {q} 的上升子序列的个数。

很容易想到 O(N4) 的naive dp.

采用点值优化,其实就是要求

F_{n,m}=\sum_{k\geq0}\binom{n}{k}\binom{m}{k}c^k .对于每种 c ,有F_{0\leq n\leq N,0\leq m\leq N} 有待解决(nN在这里不一样,N 指的是原题中的 n) .

\sum_{i,j\geq 0}F_{i,j}u^iv^j=\sum_{k\geq 0}\frac{u^k}{(1-u)^{k+1}}\frac{v^k}{(1-v)^{k+1}}c^k=\frac{1}{1-u-v-(c-1)uv}\\ F_{i,j}=F_{i-1,j}+F_{i,j-1}+(c-1)F_{i-1,j-1}\\

时间复杂度 O(N^3) .