NOIP模拟 杆子的排列 【动态规划】

杆子的排列 【动态规划】"/>

NOIP模拟 杆子的排列 【动态规划】

【题目描述】
有高为 1，2，…，n 的 n 根杆子排成一排，从左向右能看到 L 根，从右向左能看到 R 根。
求有多少种可能的排列方式。
【输入格式】
多组数据，第一行一个数 T，表示数据组数。
接下来 T 行，每行三个数 n，L，R，含义如题目描述。
【输出格式】
共 T 行，每行一个数，表示答案。答案可能很大，请对 998244353 取模。
【输入样例】
1
4 1 2
【输出样例】
2
【样例解释】
存在两种情况，分别为{4,1,2,3},{4,2,1,3}。
【数据范围】
对于 30%的数据：T≤5；n≤10；
对于 100%的数据：T≤1000；n<=200。

解题思路：

设f[i][l][r]表示已经排列了高度为1~i的杆子，从左可以看到l根，从右可以看到r根的方案数。
假设我们已经知道了f[i-1]的所有情况，那么若只排列高度为2~i的杆子的方案数也是一样的，所以求f[i]就相当于向f[i-1]中插入一根高度为1的杆子。则得出转移方程：
f[i][l][r]=f[i-1][l-1][r]（插最左边）+f[i-1][l][r-1]（插最右边）+f[i-1][l][r]*(i-2)（插中间任意一处）。
先O( n3 $n^3$)预处理，就可以O(1)查询了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#define ll long long
using namespace std;int getint()
{int i=0,f=1;char c;for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());if(c=='-')f=-1,c=getchar();for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0';return i*f;
}const int N=205,p=998244353;
int T,n,L,R;
ll f[N][N][N];void pre()
{f[1][1][1]=1;for(int i=2;i<=200;i++)for(int l=1;l<=i;l++)for(int r=1;r<=i;r++)f[i][l][r]=(f[i-1][l-1][r]+f[i-1][l][r-1]+1ll*f[i-1][l][r]*(i-2)%p)%p;
}int main()
{//freopen("pole.in","r",stdin);//freopen("pole.out","w",stdout);pre();T=getint();while(T--){n=getint(),L=getint(),R=getint();cout<<f[n][L][R]<<'\n';}return 0;
}