QOJ.ac
QOJ
Time Limit:
2 s
Memory Limit:
512 MB
GP of IMO
J. Joke
题解 by @ezoilearner,你可以通过以下联系方式联系作者:
- QQ: 2939863838
题意:我们称三运组 (p,q,s) 合法当且仅当村存在矩阵 a2×n:
0
p,q 是个 长为 n 的排列,s 是一个长为 n 的 01 字符串。
1
1−2∗n 的整数在里面恰好出现一次;
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) 的和。
n≤100
题解:可以认为 {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} 有待解决(n和N在这里不一样,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) .