#P18111. Binary Rotations
Binary Rotations
Binary Rotations
合法表达式按以下规则定义:x 是合法表达式;若 合法,(AB) 也合法。因此每个表达式对应一棵满二叉树,x 对应叶子,一对括号对应一个内部结点。
一次操作可将任意子表达式 ((AB)C) 改为 (A(BC)),其中 都合法。操作只允许这个方向。
给定 ,将所有恰有 个 x 的合法表达式,按字符顺序 ( < x < ) 排成字典序,记为 ,其中
再给定 的排列 。计算满足 且能够从 经过零次或多次操作得到 的数对 数量。
输入格式
第一行整数 ,。第二行 个整数 ,构成 的排列。最大 。
输出格式
输出满足条件的数对数量。
样例
4
3 1 5 2 4
3
时依次为 (((xx)x)x)、((x(xx))x)、((xx)(xx))、(x((xx)x))、(x(x(xx)))。一次操作可以从1到2或3,从2到4,从3或4到5。计入的数对为 。