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.
采用点值优化,其实就是要求
Fn,m=∑k≥0(nk)(mk)ck .对于每种 c ,有F0≤n≤N,0≤m≤N 有待解决(n和N在这里不一样,N 指的是原题中的 n) .
∑i,j≥0Fi,juivj=∑k≥0uk(1−u)k+1vk(1−v)k+1ck=11−u−v−(c−1)uvFi,j=Fi−1,j+Fi,j−1+(c−1)Fi−1,j−1
时间复杂度 O(N3) .