QOJ.ac

QOJ

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

# 1839. Joke

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.

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

Fn,m=k0(nk)(mk)ck .对于每种 c ,有F0nN,0mN 有待解决(nN在这里不一样,N 指的是原题中的 n) .

i,j0Fi,juivj=k0uk(1u)k+1vk(1v)k+1ck=11uv(c1)uvFi,j=Fi1,j+Fi,j1+(c1)Fi1,j1

时间复杂度 O(N3) .