---

$\mathbb{S}\mathbb{O}\mathbb{L}\mathbb{U}\mathbb{T}\mathbb{I}\mathbb{O}\mathbb{N}$

状态: $F[i,j]表示前i项,递增序列最后一个元素为A_i的方案,递减序列最后一个元素为A_j的方案$ $G[i,j]表示前i项,递减序列最后一个元素为A_i的方案,递增序列最后一个元素为A_j的方案$

$Ask:为什么要另外开一个G[][]状态?$ $Answer:说完转移后,自会提到.$

转移:

注: $1<=j<i<=N$

$i$ 与 $i-1$ 同属一个序列,

$A_{i-1}<A_i$, $F[i,j]+=F[i-1,j]$;$A_{i-1}>A_i$, $G[i,j]+=G[i-1,j]$.

$i$ 与 $i-1$ 不同属一个序列,

$A_j<A_i$, $F[i,i-1]+=G[i-1,j](F[j,i-1])$$A_j>A_i$, $G[i,i-1]+=F[i-1,j](G[j,i-1])$

$看到情况2的括号了吗?$ $这些状态在转移时还没有值,所以额外开了G[][]来使得$$转移可行$

至此已经完成了 $\mathcal{O}({\mathcal{N}}^2)$ 的算法, 使用树状数组滚动即可优化为$\mathcal{O}(nlogn)$

---

可能会出现 不存在某种序列 的情况, 所以要进行特殊处理, 代码中已用 $\#$ 注释

---

$\mathbb{C}\mathbb{O}\mathbb{D}\mathbb{E}$

#include<bits/stdc++.h> #define reg register int read(){ char c; int s = 0, flag = 1; while((c=getchar()) && !isdigit(c)) if(c == '-'){ flag = -1, c = getchar(); break; } while(isdigit(c)) s = s*10 + c-'0', c = getchar(); return s * flag; } const int maxn = 1500006; const int mod = 666623333; int N; int M; int A[maxn]; struct Tree{ int tap[maxn], v[maxn], tim; void Modify(int k, int x){ while(k <= N){ if(tap[k] != tim) tap[k] = tim, v[k] = 0; v[k] += x; if(v[k] >= mod) v[k] -= mod; k += k & -k; } } int Query(int k){ int s = 0; while(k >= 1){ if(tap[k] != tim) tap[k] = tim, v[k] = 0; s += v[k]; if(s >= mod) s -= mod; k -= k & -k; } return s; } } Ft, Gt; int flag_1, flag_2; // 1↑ 2↓ int main(){ freopen("perm.in", "r", stdin); freopen("perm.out", "w", stdout); N = read(); for(reg int i = 1; i <= N; i ++) A[i] = read(); Ft.Modify(1, 1), Gt.Modify(1, 1); flag_1 = flag_2 = 1; // # for(reg int i = 2; i <= N; i ++){ int tmp_1 = Ft.Query(N-A[i]+1), tmp_2 = Gt.Query(A[i]); if(A[i-1] < A[i]) flag_1 = 0, Gt.tim ++; // # else flag_2 = 0, Ft.tim ++; // # Ft.Modify(N-A[i-1]+1, tmp_2), Gt.Modify(A[i-1], tmp_1); } printf("%d\n", (Ft.Query(N)+Gt.Query(N)-flag_1-flag_2)%mod); return 0; }