题解

思路

把排列看成每个点 $i$ 向 $P_i$ 连边得到的若干有向环，并删去所有不递增边。

做法

剩余图由若干严格递增路径组成，同一路径上所有点的 $F(P)$ 值都等于路径终点。因此，对每个在 $A$ 中出现的值 $t$，所有满足 $A_i=t$ 的位置按升序唯一确定一条路径，而且最后一个位置必须恰为 $t$；否则答案为零。

设这些路径的起点为 $s$、终点为 $t$。还需把每个终点连向一个起点形成若干环，删去的边必须满足 $t\ge s$，所以问题变成满足该不等式的完美匹配计数。从 $N$ 到 $1$ 扫描，遇到终点便加入可用集合，遇到起点时可任选当前任一可用终点，乘上可选数量后删去一个。

复杂度

时间复杂度为 $O(N)$，空间复杂度为 $O(N)$。