题目描述

有一个长度为nnn的序列aaa，现在对数列进行一些变换，每次可以选择一对i,ji,ji,j，满足1≤iaja_i>a_jai​>aj​，然后将aia_iai​和aja_jaj​交换。如果序列bbb可以由序列aaa经过若干次变换得到，那么称bbb是可达的。求有多少种不同的可达的序列，输出答案模100000000710000000071000000007。

输入格式

第一行一个数nnn，接下来一行nnn个数，分别为a1,a2,…,ana_1,a_2,\dots,a_na1​,a2​,…,an​，保证这是nnn的一个排列。

输出格式

输出一个整数，表示答案对100000000710000000071000000007取模后的值。

样例输入

4
2 4 1 3

样例输出

8

样例解释

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

数据范围

对于20%20\%20%的数据，1≤n≤101\leq n\leq 101≤n≤10
对于40%40\%40%的数据，1≤n≤151\leq n\leq 151≤n≤15
对于100%100\%100%的数据，1≤n≤201\leq n\leq 201≤n≤20

题解

我们来考虑一下序列可达的条件是什么。

如果这不是nnn的排列，而是010101序列的话，那么条件很显然：对于任意的iii，序列bbb从右往左的第iii个111都位于序列aaa从右往左的第iii个111的右边（不一定严格，可以在同一个位置），那么aaa就可以到达bbb。

对于一个排列aaa以及一个数kkk，把aaa中大于等于kkk的数标为111，剩下的数标为000，那么就能得到一个010101序列。如果对于任意的kkk，排列aaa对应的010101序列都能够到达排列bbb，那么排列aaa就能到达排列bbb。

如果排列bbb不满足条件，那么排列aaa一定不能到达排列bbb。但为什么只要排列bbb满足条件，排列aaa就一定能够到达排列bbb呢？

我们可以让iii从111到nnn，每次将数字iii移到目标位置，令当前位置为lll，目标位置为rrr，当前(l,r](l,r](l,r]区间的最大数字为aja_jaj​，则让ala_lal​和aja_jaj​交换即可。

那要怎么实现呢？

设fi,jf_{i,j}fi,j​表示当前从大到小放到第iii个数字，且按大于等于iii为111，小于iii为000来构成的010101串为jjj，此时的方案数。要保证在枚举过程中010101串要满足上面的条件。一开始是全000的010101串，答案是全111的010101串。

时间复杂度为O(n⋅2n)O(n \cdot 2^n)O(n⋅2n)。

code

#include
using namespace std;
int n,tot=0,a[25],d[2000005],l[2000005],r[2000005];
long long f[25][1<<20];
long long mod=1000000007;
void add(int xx,int yy){l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;
}
int gt(int s){int re=0;while(s){re+=s&1;s>>=1;}return re;
}
bool pd(int s,int t){int w=0;for(int i=n;i>=1;i--){if(t&(1<=s) --w;if(w<0) return 0; }return 1;
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int s=0;s<(1<add(gt(s),s);}f[n+1][0]=1;for(int s=n;s>=1;s--){for(int i=r[n-s+1];i;i=l[i]){if(!pd(s,d[i])) continue;for(int j=1;j<=n;j++){if(d[i]&(1<f[s][d[i]]=(f[s][d[i]]+f[s+1][d[i]^(1<