Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int BASE = int(1e9) + 7;

int theCount(vector <int> p) 
{
    int n = p.size(), maxLeft[111], minRight[111];
    long long c[111][111], f[111][111];

    for (int i = 0; i <= 100; i++)
        for (int j = 0; j <= 100; j++)
            c[i][j] = j ? (c[i - 1][j] + c[i - 1][j - 1]) % BASE : 1;

    for (int i = 0; i < n; i++) f[i][i] = 1;
    for (int len = 2; len <= n; len++)
        for (int i = 0; i + len <= n; i++)
        {
            int j = i + len - 1;
            f[i][j] = 0;

            maxLeft[i] = p[i];
            for (int k = i + 1; k <= j; k++) maxLeft[k] = max(maxLeft[k - 1], p[k]);
            minRight[j] = p[j];
            for (int k = j - 1; k >= i; k--) minRight[k] = min(minRight[k + 1], p[k]);

            vector <int> q(p.begin() + i, p.begin() + j + 1);
            sort(q.begin(), q.end());

            for (int k = i; k < j; k++)
                if (maxLeft[k] == q[k + 1 - i] && minRight[k + 1] == q[k - i])
                {
                    f[i][j] += f[i][k] * f[k + 1][j] % BASE * c[j - i - 1][k - i];
                    f[i][j] %= BASE;
                }
        }

    return f[0][n - 1];
}

int main()
{
    int n, x;
    vector <int> p;
    cin >> n;
    while (n--) cin >> x, p.push_back(x);
    cout << theCount(p) << endl;
}

Code mẫu của happyboy99x

#include<bits/stdc++.h>
using namespace std;

#define TR(v,i) for(__typeof((v).begin())i=(v).begin();i!=(v).end();++i)
#define all(a) (a).begin(), (a).end()
template<class T> int size(const T &a) { return (int) a.size(); }

class AdjacentSwaps {
    static const int N = 100, MOD = 1e9+7;
    int f[N][N], mx[N][N][2], mn[N][N][2], c[N][N], n;

    void init() {
        memset(mn, 0x3f, sizeof mn);
        memset(mx, 0xc1, sizeof mx);
        memset(f, 0, sizeof f);
        memset(c, 0, sizeof c);
        c[0][0] = 1;
        for(int i = 1; i < N; ++i) {
            c[i][0] = 1;
            for(int j = 1; j <= i; ++j)
                c[i][j] = (c[i-1][j-1] + c[i-1][j]) % MOD;
        }
    }

    public:
    int theCount(vector <int> p) {
        n = size(p);
        init();
        for(int i = 0; i < n; ++i)
            f[i][i] = 1, mx[i][i][0] = mn[i][i][0] = p[i];
        for(int len = 2; len <= n; ++len)
            for(int i = 0, j = len-1; j < n; ++i, ++j) {
                for(int k = i; k <= j; ++k) {
                    if(p[k] < mn[i][j][0]) mn[i][j][1] = mn[i][j][0], mn[i][j][0] = p[k];
                    else if(p[k] < mn[i][j][1]) mn[i][j][1] = p[k];
                    if(p[k] > mx[i][j][0]) mx[i][j][1] = mx[i][j][0], mx[i][j][0] = p[k];
                    else if(p[k] > mx[i][j][1]) mx[i][j][1] = p[k];
                }
                for(int k = i; k <= j-1; ++k)
                    if(mn[k+1][j][0] < mx[i][k][0] && mn[k+1][j][0] > mx[i][k][1] && mx[i][k][0] < mn[k+1][j][1])
                        f[i][j] = (f[i][j] + 1LL * f[i][k] * f[k+1][j] % MOD * c[j-i-1][k-i] % MOD) % MOD;
            }
        return f[0][n-1];
    }
};

int main() {
    ios::sync_with_stdio(false);
    int n; vector<int> a;
    cin >> n; for(int i = 0, x; i < n; ++i) cin >> x, a.push_back(x);
    cout << AdjacentSwaps().theCount(a) << endl;
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>

using namespace std;

const int N = 111;
const int MOD = 1000000007;

int a[N];
int Left[N], Right[N];
int S[N][N], comb[N][N];
int n, m;
long long memo[N][N];

long long dp(int L, int R, int j) {
    long long &ans = memo[L][j];
    if (ans != -1) return ans;
    if (L == R) return ans = 1;
    if (Left[j] != j - 1)
        ans = dp(L, R, j - 1);
    else
        ans = 0;
    for (int i = L; i < R; ++i) 
    if (L == i || S[i][i] > 1) {
        int L_size = S[L][i] - 1;
        int R_size = S[i + 1][R - 1] + (j - Left[j]);
        ans += dp(L, i, Right[i] - 1) * dp(i + 1, R, j) % MOD * comb[L_size + R_size][L_size] % MOD;
        if (ans >= MOD) ans -= MOD;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("C11SWAP.txt", "r", stdin);
#endif
    cin >> n;
    for (int i = 0; i< n; ++i) cin >> a[i];
    bool fail = 0;
    vector<int> C;
    for (int i = 0; i < n; ++i) {
        bool passed = 0;
        for (int j = 0; j < n; ++j) if (a[j] == i) {
            if (j > i) {
                C.push_back(j - i);
                for (int k = j; k > i; --k)
                    a[k] = a[k - 1];
                a[i] = i;
            }
            passed = j >= i;
            break;
        }
        if (!passed) {
            fail = 1;
            break;
        }
    }
    fail |= accumulate(C.begin(), C.end(), 0) != n - 1;
    if (fail) {
        cout << 0 << endl;
        return 0;
    }
    m = C.size();
    int sum = 0;
    for (int i = 0; i < m; ++i) {
        for (int j = sum + 1; j <= sum + C[i]; ++j)
            Left[j] = sum;
        sum += C[i];
        Right[i] = sum;
    }
    for (int i = 0; i < m; ++i) {
        S[i][i] = C[i];
        for (int j = i + 1; j < m; ++j)
            S[i][j] = S[i][j - 1] + C[j];
    }
    for (int i = 0; i <= n; ++i) {
        comb[i][0] = 1;
        if (i == 0) continue;
        for (int j = 1; j <= i; ++j)
            comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % MOD;
    }
    memset(memo, -1, sizeof(memo));
    long long ans = dp(0, m - 1, n - 1);
    cout << ans << endl;
    return 0;
}

Code mẫu của RR

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>

#define FOR(i,a,b) for(int i=(a),_b=(b); i <= _b; ++i)
#define FORD(i,a,b) for(int i=(a),_b=(b); i >= _b; --i)
#define REP(i,a) for(int i=0,_a=(a); i < _a; ++i)
using namespace std;

const long long MOD = 1000000007;
const int oo = 1000111;

long long f[111][111];
int c[111][111], min1[111][111], min2[111][111], max1[111][111], max2[111][111];
int n, a[111];

bool order(int a, int b, int c, int d) {
    return a < b && b < c && c < d;
}

int solve() {
    FORD(i,n,1) FOR(j,i,n) {
        if (i == j) {
            f[i][j] = 1;
        }
        else {
            f[i][j] = 0;
            FOR(k,i,j-1)
            if (order(max2[i][k], min1[k+1][j], max1[i][k], min2[k+1][j])) {
                f[i][j] += f[i][k] * f[k+1][j] % MOD * c[j-i-1][k-i] % MOD;
                f[i][j] %= MOD;
            }
        }
    }
    return f[1][n];
}

int main() {
    scanf("%d", &n); FOR(i,1,n) scanf("%d", &a[i]);
    c[0][0] = 1;
    FOR(i,1,100) {
        c[i][0] = 1;
        FOR(j,1,i) c[i][j] = (c[i-1][j-1] + c[i-1][j]) % MOD;
    }

    FORD(i,n,1) FOR(j,i,n) {
        if (i == j) {
            min1[i][j] = a[i];
            min2[i][j] = oo;

            max1[i][j] = a[i];
            max2[i][j] = -oo;
        }
        else {
            min1[i][j] = min1[i][j-1];
            min2[i][j] = min2[i][j-1];

            max1[i][j] = max1[i][j-1];
            max2[i][j] = max2[i][j-1];

            if (a[j] < min1[i][j]) {
                min2[i][j] = min1[i][j];
                min1[i][j] = a[j];
            }
            else if (a[j] < min2[i][j]) {
                min2[i][j] = a[j];
            }

            if (a[j] > max1[i][j]) {
                max2[i][j] = max1[i][j];
                max1[i][j] = a[j];
            }
            else if (a[j] > max2[i][j]) {
                max2[i][j] = a[j];
            }
        }
    }
    cout << solve() << endl;
}

Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(typeof(n) i = 0; i < (n); ++i)
#define Repd(i,n) for(typeof(n) i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(typeof(b) i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(typeof(a) i = (a); i >= (b); --i)
#define Fit(i,v) for(typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define Fitd(i,v) for(typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))
#define nl puts("")
#define sp printf(" ")
#define ok puts("ok")
//#include <conio.h>

template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; }
template<class T> void db(T a, int p = -1) { if (p >= 0) cout << fixed << setprecision(p); cout << a << " "; }
template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> T sqr(T x) { return x * x; }
template<class T> T cube(T x) { return x * x * x; }
template<class T> struct Triple { T x, y, z; Triple() {} Triple(T _x, T _y, T _z) : x(_x), y(_y), z(_z) {} };
template<class T> Triple<T> euclid(T a, T b) { if (b == 0) return Triple<T>(1, 0, a); Triple<T> r = euclid(b, a % b); return Triple<T>(r.y, r.x - a / b * r.y, r.z); }
template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); }
const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0;
char gc() { if (rsz <= 0) { ptr = 0; rsz = fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; }
void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); }
int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; }
template<class T> bool gi(T &v) {
    v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc();
    while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true;
}

const double PI = 2 * acos(0);
const string months[] = {"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"};
const int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int dr[] = {-1, 0, +1, 0};
const int dc[] = {0, +1, 0, -1};
const int inf = (int)1e9 + 5;
const ll linf = (ll)1e16 + 5;
const double eps = 1e-9;
const ll mod = 1000000007;
typedef pair<int, int> II;

int n, a[111];
int l[111][111], r[111][111];
ll f[111][111], C[111][111];

ll go(int u, int v){
    if(f[u][v] != -1) return f[u][v];
    if(u == v) return f[u][v] = 1;
    ll &res = f[u][v];
    res = 0;
    int t[111];
    For(i, u, v) t[i] = a[i];
    t[u] = l[u][v]; t[v] = r[u][v];
    for(int i = u; i < v; i++){
        if(l[i + 1][v] == t[i] && r[u][i] == t[i + 1])
            res = (res + (go(u, i) * go(i + 1, v)) % mod * C[i - u][v - u - 1]) % mod;
    }
   // cout << u << " " << v << " " << res << endl;
    return res;
}

int main(){
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    scanf("%d", &n);
    Rep(i, n) scanf("%d", &a[i]);
    ms(l, -1); ms(r, -1); ms(C, 0);
    Rep(i, 101) C[0][i] = 1;
    For(i, 1, 100) For(j, 1, i) C[j][i] = (C[j][i - 1] + C[j - 1][i - 1]) % mod;

    Rep(i, n) { l[i][i] = i; r[i][i] = i;}
    Rep(i, n) For(j, i + 1, n - 1){
        if(i == 0) l[i][j] = a[0];
        else{
            Rep(k, i) if(a[k] >= i && a[k] <= j){
                if(l[i][j] == -1) l[i][j] = a[k];
                else if(l[i][j] > -1) l[i][j] = -2;
            }
        }
        if(j == n - 1) r[i][j] = a[n - 1];
        else{
            For(k, j + 1, n - 1) if(a[k] >= i && a[k] <= j){
                if(r[i][j] == -1) r[i][j] = a[k];
                else if(r[i][j] > -1) r[i][j] = -2;
            }
        }
    }
    ms(f, -1);
    cout << go(0, n - 1);
  //  cout << clock();
}

Code mẫu của skyvn97

#include<cstdio>
#include<cstdlib>
#define MAX   333
const int mod=(int)1e9+7;
int c[MAX][MAX];
int f[MAX][MAX];
int q[MAX];
int n;
void init(void) {
    scanf("%d",&n);
    int i,t;
    for (i=1;i<=n;i=i+1) {
        scanf("%d",&t);
        q[t+1]=i;
    }
    for (i=1;i<=n;i=i+1)
        if (q[i]==i) {
            printf("0");
            exit(0);
        }
}
void construct(void) {
    int i,j;
    for (i=1;i<=n;i=i+1)
        for (j=1;j<=n;j=j+1)
            c[i][j]=0;
    for (i=1;i<=n;i=i+1) {
        if (q[i]<i) {
            c[q[i]][q[i]-1]=1;
            for (j=q[i];j<i-1;j=j+1) c[j][j+1]=1;
            c[i][i-1]=1;
        }
        if (q[i]>i) {
            c[q[i]-1][q[i]]=1;
            for (j=q[i]-1;j>i;j=j-1) c[j][j-1]=1;
            c[i-1][i]=1;
        }   
    }
    for (i=1;i<n-1;i=i+1)
        if (c[i][i+1]>0 && c[i+1][i]>0) {
            printf("0");
            exit(0);
        }
}
void optimize(void) {
    int i,j,k;
    n--;
    for (i=1;i<=n;i=i+1)
        for (j=1;j<=n;j=j+1)
            f[i][j]=0;
    f[1][1]=1;
    for (i=1;i<n;i=i+1)
        for (j=1;j<=i;j=j+1) {
            if (c[i][i+1]>0) {
                for (k=j+1;k<=i+1;k=k+1) f[i+1][k]=(f[i+1][k]+f[i][j])%mod;             
                continue;
            }
            if (c[i+1][i]>0) {
                for (k=1;k<=j;k=k+1) f[i+1][k]=(f[i+1][k]+f[i][j])%mod;
                continue;
            }
            for (k=1;k<=i+1;k=k+1) f[i+1][k]=(f[i+1][k]+f[i][j])%mod;
        }           
    int res=0;
    for (i=1;i<=n;i=i+1) res=(res+f[n][i])%mod;
    printf("%d",res);
}
int main(void) {
    init();
    construct();
    optimize();
    return 0;
}