题解 by @ezoilearner，你可以通过以下联系方式联系作者：
- QQ: 2939863838
题意：我们称三运组 $(p,q,s)$ 合法当且仅当村存在矩阵 $a_{2\times n}$：
0 $p,q$ 是个 长为 $n$ 的排列，$s$ 是一个长为 $n$ 的 $01$ 字符串。
1 $1-2*n$ 的整数在里面恰好出现一次；
2 $\forall i,j,[a_{1,i} < a_{1,j}]=[p_i < p_j]$ .
3 $\forall i,j,[a_{2,i} < a_{2,j}]=[q_i < q_j]$ .
4 $\forall i,a_{1,i} < a_{2,i}=[s_i=0]$ .
$f(p,q)$ 定义为满足条件的 $s$ 的个数。
给定 $p$ ,给定 $q$ 的若干位置，求对于所有满足条件的 $q$ ,$f(p,q)$ 的和。
$n\leq 100$
题解:可以认为 $\{p\}={1,2,\cdots,N}$ .
这样情况下，不能存在 $i>j,q_i < q_j,s_i=0,s_j=1$ ,其实这也是充分条件。
进而考虑 $f(p,q)$ 的计算，其实就是 $\{q\}$ 的上升子序列的个数。
很容易想到 $O(N^4)$ 的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)$ .