# Codeforces 1763D Valid Bitonic
> https://codeforces.com/contest/1763/problem/D

題意為給$[1,n]$序列$B$，問說總共有幾個bitonic序列使得$B_i = x$且$B_j = y$，題目表示bitonic序列為單峰序列且最高點在$[2, n-1]$之間。有$t$組數據，$1 \le t \le 100$，$1 \le n \le 100$。

不失一般性假設$i \lt j$且$x \lt y$，如果$x \gt y$的話變換一下就好($swap(x, y),\ i=n-j+1,\ j=n-i+1$)，直接組合?超難==，可以看解答：
> https://codeforces.com/blog/entry/110278

這題可以用DP想==，難死我了==，筆記一下。

如果我們考慮從$1$開始放進序列裡的話，一定只能從左右邊照順序放，那我們可以定義$dp(a, b, c)$為長度為$n$的空序列中，放入了$1$到$a$，且左邊放了$b$個，右邊放了$c$個的方法數，
如果沒有限制的話，因為$b+c=a$和$dp(0,0,0)=1$直接嚕上去複雜度$O(n^2)$，轉移就$dp(a, b, c) = dp(a-1, b-1, c) + dp(a-1, b, c-1)$。

如果放到$x$了，根據限制他只能放在位置$i$上，故轉移為$dp(x, i, c) = dp(x-1, i-1, c)$，沒其他可能。

再來如果放到$y$了，那麼$y$可以在左邊也可以在右邊，注意一下$y$的位置為$j$：
(1) $y$在左邊$dp(y, j, c) = dp(y-1, j-1, c)$，
(2) $y$在右邊$dp(y, b, n-j+1) = dp(y-1, b, n-j)$。

然後還要注意的是如果放到$n$了，$n$一定不能在最左和最右。

最後答案就是$\sum_{l=1}^{n-1} dp(n, l, n-l)$，但是這樣算的話是會重複的，放$n$時可以在左邊或右邊，所以除以二就好。

#include <bits/stdc++.h>
#pragma GCC optimize(3)
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define F first
#define S second
#define endl '\n'
using namespace std;
const int inf = 0x3f3f3f3f;
const ll Inf = 1e18;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;

const int maxn =  5;

ll inv[maxn];
void init(){
    inv[0] = inv[1] = 1;
    for(int i=2; i<maxn; i++){
        inv[i] = mod - mod/i * inv[mod%i] % mod;
    }
    return;
}

// dp(i, j, k) : 放1到i，左邊放j個，右邊放k個
ll dp[101][101][101];

void solve(){
    int n, i, j, x, y; cin >> n >> i >> j >> x >> y;
    if(i >= j){
        swap(i, j);
        swap(x, y);
    }
    if(x >= y){
        i = n - i + 1;
        j = n - j + 1;
        swap(i, j);
        swap(x, y);
    }
    if(y == n && j == n){
        cout << 0 << endl;
        return;
    }

    memset(dp, 0, sizeof dp);
    dp[0][0][0] = 1;
    for(int a=1; a<=n; a++){
        for(int b=0; b<=a; b++){
            if(a == x && b != i) continue;
            int c = a - b;
            if(a == y && b != j && c != n - j + 1) continue;
            if(a == n && (b == 1 || c == 1)){
                if(b == 1) dp[a][b][c] = dp[a-1][b][c-1];
                if(c == 1) dp[a][b][c] = dp[a-1][b-1][c];
                continue;
            }
            if(a == x){
                dp[a][b][c] = dp[a-1][b-1][c];
            }
            else if(a == y){
                if(b == j) dp[a][b][c] = dp[a-1][b-1][c];
                if(c == n - j + 1) dp[a][b][c] = dp[a-1][b][c-1];
            }
            else{
                dp[a][b][c] += dp[a-1][b][c-1] + dp[a-1][b-1][c];
                dp[a][b][c] %= mod;
            }
        }
    }
    
    ll ans = 0;
    for(int i=1; i<=n-1; i++) ans = (ans + dp[n][i][n-i]) % mod;
    ans = ans * inv[2] % mod;
    cout << ans << endl;
} 
 
 
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    init();
    int t = 1;
    cin >> t;
    while(t--)
    solve();
 
    return 0;
}

### 時間複雜度 ：$O(tn^2)$
###### tags: `dp`