Valid Bitonic Permutations - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题意转化一下：先考虑如何构造一个双调的序列。
本题的解题核心是：如何构造出双调的序列？（主要是这个技巧要知道）
那么如何构造呢？
首先来看 1 ，可以放在最左边，也可以放在最右边。
2，同理，在1的基础上，可以放在左边，可以放在右边
其他数也是一样。(主要是这个构造的思想，没做过构造一个双调的序列不容易想出来)
所以对于 数字 num 来说，可以放在L位置，或者R位置
这便可以用dfs(num,L,R)来进行记忆化搜索dp。
根据L，R可以推出 num 便可以优化 num 维度
这便是构造出普通的双调的序列的方案数的dfs
ll dfs(int l,int r) { int num=(l-1)+(n-r)+1; if(l==r&&l!=1&&l!=n) return 1; if(dp[l][r]!=-1) return dp[l][r]; ll ans=0; ans=(ans+dfs(l+1,r))%MOD; ans=(ans+dfs(l,r-1))%MOD; return dp[l][r]=ans; }
接下来在把题目的要求放进去即可：
注意 L==R的地方不能是 1 和 n，因为这两种情况是单峰序列(题目要求也有提及)
// LUOGU_RID: 108705056 #include<bits/stdc++.h> using namespace std; #define ll long long #define mp make_pair #define pb push_back #define popb pop_back #define fi first #define se second #define popcount __builtin_popcount #define popcountll __builtin_popcountll const int N=110; const ll MOD=1e9+7; //const int inf=1e9; //const ll INF=1e18; int T,n,posa,posb,x,y; ll dp[N][N]; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f; } int check(int pos,int num) { if(pos==posa) return num==x; else if(pos==posb) return num==y; return 1; } ll dfs(int l,int r) { int num=(l-1)+(n-r)+1; if(l==r) { if(check(l,num)&&l!=1&&l!=n) return 1; return 0; } if(dp[l][r]!=-1) return dp[l][r]; ll ans=0; ans=(ans+check(l,num)*dfs(l+1,r))%MOD; ans=(ans+check(r,num)*dfs(l,r-1))%MOD; return dp[l][r]=ans; } int main() { // freopen("","r",stdin); // freopen("","w",stdout); // ios::sync_with_stdio(0); // cin.tie(0); T=read(); while(T--) { n=read(),posa=read(),posb=read(),x=read(),y=read(); memset(dp,-1,sizeof(dp)); printf("%lld\n",dfs(1,n)); } return 0; }