Skip to content

1270: 可达排列

题目

题目描述

渣渣辉手里有一个数列 $a[1..n]$,它是 $1, 2, ..., n$ 的一个排列。

现在渣渣辉想对这个数列进行一些变换:每一次他可以选择一对 $i, j$,满足$1 \leq i < j \leq n$ 且 $a[i] > a[j]$,然后将 $a[i]$ 和 $a[j]$ 交换。

如果一个排列 $b[1..n]$ 可以由初始数列 $a$ 经过若干次变换而得到,那么渣渣辉就称b是可到达的。

现在渣渣辉想知道,有多少种不同的可到达排列。

由于答案可能很大,你只需要输出答案模$10^9+7$后的结果。

输入格式

第一行一个整数 $n$。

接下来一行是空格隔开的 $n$ 个整数,$a[1], a[2], ..., a[n]$,保证它是一个 $n$ 排列。

输出格式

输出一行答案对模 $10^9+7$ 后的结果。

样例输入

text 4 2 4 1 3

样例输出

text 8

  • 可达的排列有2413, 2314, 2143, 2134, 1423, 1243, 1324, 1234。

数据范围

时间限制:1000 ms 空间限制:512 mb

全局限制

  • $1 \leq n \leq 20$

部分限制

  • $(\text{40 points})~ n \leq 10$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!