【NOIP模拟】 (10.23) T2 杆子的排列

杆子的排列"/>

【NOIP模拟】 (10.23) T2 杆子的排列

杆子的排列

题目描述：        有高为1,2,......,n的n根杆子排成一排，从左向右能看到L根，从右向左能看到R根。求有多少种可能的排列方式。
输入格式：        多组数据，第一行一个T，表示数据组数。        接下来T行，每行三个数n，L，R，含义如题目描述。
输出格式：        共T行，每行三个数，表示答案。答案要取模998244353
数据范围：        对于30%的数据：T<=5;n<=10;        对于100%的数据：T<=1000;n<=200
解析：        动态规划经典题型。        考虑已经插入高度为2~i的杆子再插入高度为1的杆子，会出现三种情况：        1.插在左边，则只有左边能看到。        2.插在右边，则只能右边能看到。        3.插在中间，则两边都看不到。        设f[i][j][k]表示插入1~i的杆子，左边能看到j根，右边能看到k根的方案数。        则有f[i][j][k]=f[i-1][j][k]*(i-2)+f[i-1][j-1][k]+f[i-1][j][k-1]。        f[i-1][j][k]*(i-2)表示将杆子插在中间        f[i-1][j-1][k]表示将杆子插在左边        f[i-1][j][k-1]表示将杆子插在右边        注意初始化：f[1][1][1]=1。
代码：

#include <bits/stdc++.h>
using namespace std;const int mod=998244353;
const int Max=210;
long long t,n,L,R;
long long f[Max][Max][Max];inline int get_int()
{int x=0,f=1;char c;for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());if(c=='-') {f=-1;c=getchar();}for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';return x*f;
}int main()
{//freopen("pole.in","r",stdin);//freopen("pole.out","w",stdout);f[1][1][1]=1;for(register int i=2;i<=200;i++)for(register int j=1;j<=i;j++)for(register int k=1;k<=i;k++){f[i][j][k]=f[i-1][j][k]*(i-2);if(j>1) f[i][j][k]+=f[i-1][j-1][k];if(k>1) f[i][j][k]+=f[i-1][j][k-1];f[i][j][k]%=mod;}t=get_int();while(t--){n=get_int();L=get_int();R=get_int();cout<<f[n][L][R]<<"\n";}return 0;
}