天才题目

详细说一说我自己的思考过程，以及看完题解后的震撼思路

首先我们注意到如果两个数的差距大于1，那他们的偏序关系是不可以变的

我们其实也可以不妨钦定两个数如果相等它们的偏序也是不可变得。

然后我们考虑图论建模，发现是一个$DAG$ 的拓扑计数

然后我觉得这个东西应该非常 $npc$ 于是就没再往这个方向去想

然后我考虑了一个新的想法，考虑把这些数从小到大重新放进去，那么对于一个数字 $a_i$ ，我只需要满足它对它前面有多少个 $a_i-2$， $a_i-2$， $a_i-3$ ………… 的需求即可

然后我们注意到当我们放 $a_i$ 这个数的时候，我是早已经放好 $a_i-1$ 的，然后我们发现它们有相同的前缀需求，所以我们放 $a_i$ 的时候只需要考虑 $a_i-2$ 的限制即可

本蒟蒻止步于此，觉得再想下去没有性价比，于是打开了题解。

发现题解的第一篇就是我最早想的图论建模的思路

他说，$DAG$ 计数显然是不可做的，但是我们看这个题有什么性质

注意到

注意到

注意到

注意到

注意到

！！！！！！

！！！！！！

！！！！！！

！！！！！！

我们发现，

所 有 奇 数 和 所 有 偶 数 的 偏 序关 系 是 分 别 固 定 的。

于是我们相当于是两个固定的链条相互插入

具体看代码吧

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int h[5005],f[5005][5005];
int cnt[2],pos[5005],ru[5005],reid[2][5005];
int main(){
	int T;scanf("%d",&T);
	while(T--){
		int n;scanf("%d",&n);
		cnt[1]=cnt[0]=0;
		for(int i=1; i<=n; i++){
			scanf("%d",&h[i]);
			cnt[h[i]&1]++;
			pos[i]=cnt[h[i]&1];
			reid[h[i]&1][pos[i]]=i;
			ru[i]=0;
			for(int j=i; j>=1; j--){
				if(abs(h[j]-h[i])>=2&&((h[j]^h[i])&1)){
					ru[i]=pos[j];
					break;
				}
			}
		}for(int i=0; i<=cnt[0]; i++){
			for(int j=0; j<=cnt[1]; j++){
				f[i][j]=0;
			}
		}f[0][0]=1;
		for(int i=0; i<=cnt[0]; i++){
			for(int j=0; j<=cnt[1]; j++){
				if(ru[reid[0][i+1]]<=j)f[i+1][j]=(f[i][j]+f[i+1][j])%mod;
				if(ru[reid[1][j+1]]<=i)f[i][j+1]=(f[i][j]+f[i][j+1])%mod;
//				cout<<f[i+1][j]<<" "<<f[i][j+1]<<endl;
			}
		}printf("%d\n",f[cnt[0]][cnt[1]]);
	}
	return 0;
} 

```
`