题解 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)$ .