AGC055C Weird LIS

显然，删除一个数后剩下的数的 LIS 长度和原来的差至多为 $1$ ，因此 $A$ 序列一定是由 $x-1$ 和 $x$ 构成的。

我们可以考虑对于任意一个由 $x-1$ 和 $x$ 组成的长为 $n$ 的序列，在 $x$ 取哪些数时可作为合法的 $A$ 序列。很显然，$x-1$ 的个数不超过 $x$ ，因为它们都在 LIS 上，LIS 的长度就是 $x$ 。现在我们考虑 $x$ 最大可以取多少。

我们考虑被 $x-1$ 截开的数组，假设剩下若干段，段长为 $l_1,l_2,\ldots,l_k$ ，可以发现 $x$ 最大取 $\sum_{1 \le i \le k} l_i / 2$ 。

因为对于每段中的数，我们要让它尽量可以在 LIS 中，同时可以被替代，由于一个数不能被 LIS 中的其他数替代，所以 LIS 长度是不超过 $l_i / 2$ 的。同时，我们可以构造 $2,1,4,3,…$ 交替出现，来卡到这个上界，因此 $x = \sum_{1 \le i \le k} l_i/2$ 。

接下来可以发现，对于所有最小值到最大值之间的数，$x$ 都能取到。因为我只需要在之前构造的数列的基础上，把一些数改成极小的数和极大的数即可（即在 LIS 第一个位置后就降序改成比第一个位置小的数，在前面就降序改成比第一个位置大的数）。

因此对于每个序列来讲，它会对一个区间内的 $x$ 造成影响，我们可以利用差分解决这个问题，即在每个 $x$ 的值 $t$ 加上左端点为这个数的方案个数，减去右端点为 $t-1$ 的方案个数。

左端点为 $t$ 的方案数是非常好算的，相当于有 $t$ 个位置是 $x-1$ ，就是 $\binom n t$ 。

右端点为 $t$ 的方案数就是上面那个上界为 $t$ 的方案数。我们可以设 $dp[n][i]$ 表示当前已经填入了 $n$ 个数，上界的值为 $i$ 的方案数。每次可以选择往后加入一个 $x-1$ 或加入 $x,x$ 或加入 $x,x-1$ ，三种对上限的贡献都是 $1$ 。最后的值就是 $dp[n-1][t] + dp[n][t]$ ，因为最后一个位置可为 $x$ ，这个在之前不会被计算到。

注意序列为 $1,2,3,\ldots,n$ 是特殊情况，它总是可以满足 $x=n-1$ 。

复杂度 $O(n^2)$ 。

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define mp make_pair
#define rep( i , a , b ) for( int i = (a) , i##end = b ; i <= i##end ; ++ i )
#define per( i , a , b ) for( int i = (a) , i##end = b ; i >= i##end ; -- i )
#define mem( a ) memset( a , 0 , sizeof (a) )
#define all( x ) x.begin() , x.end()
//#define int long long
// #pragma GCC optimize(2)
typedef long long ll;
const int MAXN = 5e3 + 10;
int P;
int n , m , q;

int Pow( int x , int a ) {
    int ret = 1;
    while( a ) {
        if( a & 1 ) ret = ret * 1ll * x % P;
        x = x * 1ll * x % P , a >>= 1;
    }
    return ret;
}

int dp[MAXN][MAXN];
void Inc( int& x , int y ) {
    x = ( x + y < P ? x + y : x + y - P );
}

int d[MAXN] , C[MAXN][MAXN];

void solve() {
    cin >> n >> m >> P;
    dp[0][0] = 1;
    for( int i = 1 ; i <= n ; ++ i ) for( int j = 1 ; j <= i ; ++ j ) {
        if( dp[i - 1][j - 1] ) Inc( dp[i][j] , dp[i - 1][j - 1] );
        if( i >= 2 ) {
            Inc( dp[i][j] , dp[i - 2][j - 1] * 2 % P );
        }
    }
    rep( j , 1 , n ) Inc( dp[n][j] , dp[n - 1][j] );
    // cout << dp[n][2] << endl;
    rep( i , 0 , n ) {
        C[i][0] = 1;
        rep( j , 1 , i ) C[i][j] = ( C[i - 1][j] + C[i - 1][j - 1] ) % P;
    }
    rep( i , 0 , n ) {
        Inc( d[i] , C[n][i] );
        Inc( d[i + 1] , P - dp[n][i] );
    }
    rep( i , 1 , n ) d[i] = ( d[i] + d[i - 1] ) % P;
    // rep( i , 0 , m + 1 ) cout << d[i] << endl;
    int res = ( n != 3 ) + ( m == n - 1 );
    rep( i , 3 , m ) Inc( res , d[i] );
    cout << res << endl;
}

signed main() {
	// freopen("in","r",stdin);
	// freopen("fout","w",stdout);
	// int T;cin >> T;while( T-- ) solve();
	solve();
}