Problem

给定 $n$ ，求有多少个 $1\to n$ 的排列可以分割成三个上升子序列。$n \leq 500$。

Solution

假设给定一个排列，那么我们贪心的从前往后选，维护三个上升序列，每扫到一个数字添加到能放的上升序列且保证原上升序列的最大值尽量大。这样一定能构造出一种合法方案（如果有）且分割方案唯一。

考虑三个序列的最大值设计状态。由于不清楚插入的数具体是什么，我们令其为相对大小： $f_{i, j, k}$ ，且令 $i>j>k\geq 0$ 。同时存在 $j=k=0$ 的情况。

那么我们插入一个新的相对大小为 $l \in [1, i+1]$ 的值。那么原相对大小处于 $[l, i]$ 区间的值都会被往后顶成 $[l+1, i+1]$ 。则我们分情况讨论 $l$ 的转移：

$$ f_{i, j, k} \rightarrow \begin{cases} f_{i+1, j+1, l} & \text{for } k<l\leq j\\ f_{i+1, l, k} & \text{for }j<l \leq i\\ f_{i+1, j, k} & \text{for }l=i+1 \end{cases} $$

差分即可优化到 $O(n^3)$ 。

Code

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

const int N=501;
int f[2][N][N], g[2][N][N];
int u, v=1;

int n, P;
int add(int &x, int y) { x+=y; if(x>=P) x-=P; return x; }

int main() {
    freopen("yuan.in","r",stdin);
    freopen("yuan.out","w",stdout);
    ios::sync_with_stdio(false), cin.tie(0);
    cin>>n>>P;
    f[v][0][0]=1;
    int ans=0;
    for(int i=1; i<=n; i++) {
        u^=1, v^=1;
        for(int j=0; j<i-1;j++)
        for(int k=0; k<=j; k++)
            f[v][j][k]=g[v][j][k]=0;
        for(int j=0; j<i-1; j++)
        for(int k=0; (!k && !j) || k<j; k++)
            add(f[v][j+1][k+1],f[u][j][k]),
            add(f[v][j+1][j+1],-f[u][j][k]),
            add(g[v][j+1][k],f[u][j][k]),
            add(g[v][i][k],-f[u][j][k]);
        for(int j=0; j<i; j++) 
            for(int k=0; (!k && !j) || k<j; k++)
                add(f[v][j][k],f[v][j][k-1]),
                add(g[v][j][k],g[v][j-1][k]);
        for(int j=0; j<i; j++)
            for(int k=0; (!k && !j) || k<j; k++) {
                add(f[v][j][k],add(g[v][j][k],f[u][j][k]));
                if(i==n) add(ans, f[v][j][k]);
            }
    }
    printf("%d\n", ans);
    return 0;
}