题目戳这里。

最长下降子序列单调队列求法。

\(f_{i,j,k}\)表示考虑前\(i\)个数，\(g_1 = j,g_2 = k\)的方案数。转移：

$$f_{i,j,k} = \sum_{p = k+1}^{{j}f_{i-1,p,k}+\sum_{p=0}}kf_{i-1,j,p}$$

二维前缀和优化。复杂度\(O(NK^2)\)。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cstdlib>

using namespace std;

const int maxk = 201;

int f[2][maxk][maxk],N,K,rhl,ans;

int main()

{

	freopen("1696.in","r",stdin);

	freopen("1696.out","w",stdout);

	scanf("%d %d %d",&N,&K,&rhl);

	for (int i = 1;i <= K;++i) f[1][i][0] = 1;

	for (int p = 2,now = 0,last = 1,inc;p <= N;++p,swap(now,last))

	{

		for (int i = 1;i <= K;++i)

		{

			for (int j = i-1;j >= 0;--j)

			{

				f[last][i][j] += f[last][i][j+1];

				if (f[last][i][j] >= rhl) f[last][i][j] -= rhl;

			}

			for (int j = 0;j < i;++j)

			{

				f[last][i][j] += f[last][i-1][j];

				if (f[last][i][j] >= rhl) f[last][i][j] -= rhl;

			}

		}

		memset(f[now],0,sizeof f[now]);

		for (int i = 1;i <= K;++i)

			for (int j = 0;j < i;++j)

			{

				f[now][i][j] = f[last][i][j]-f[last][j][j]-f[last][i][j+1]+f[last][j][j+1];

				while (f[now][i][j] >= rhl) f[now][i][j] -= rhl;

				while (f[now][i][j] < 0) f[now][i][j] += rhl;

				if (j)

				{

					inc = f[last][i][0]-f[last][i-1][0]-f[last][i][j+1]+f[last][i-1][j+1];

					while (inc >= rhl) inc -= rhl; while (inc < 0) inc += rhl;

					f[now][i][j] += inc; if (f[now][i][j] >= rhl) f[now][i][j] -= rhl;

				}

			}

	}

	for (int i = 1;i <= K;++i)

		for (int j = 0;j < i;++j)

		{

			ans += f[N&1][i][j];

			if (ans >= rhl) ans -= rhl;

		}

	printf("%d\n",ans+1);

	fclose(stdin); fclose(stdout);

	return 0;

}