建设城市[city]

题目描述web

球球是一位建筑师。一天，他收到市长的任务：建设城市。球球打算建造 2n 座高楼。为了保证城市美观，球球作出了以下计划：svg

1. 球球喜欢整齐的事物。他但愿高楼从左向右排成一行，编号依次为 。
2. 球球喜欢整数，他要求每座高楼的高度都是正整数。
3. 因为材料限制，高楼的高度没法超过 。
4. 球球喜欢中间高，两边低的造型。他要求前 座高楼的高度不降低，后 座高楼的高度不上升。
5. 球球打算选两座编号为 的高楼做为这座城市的地标。他认为只有当这两座高楼高度相等时，
   才会让城市变得美观。
   球球把本身的想法告诉了市长。市长但愿得知全部建设城市的方案数。两种方案不一样，当且仅当某座
   高楼的高度在两个方案中不一样。这个问题可难倒了球球。球球找到了你，但愿你能帮他算出答案。因为答案可能很大，你只须要给出答案对 998244353 取模后的结果。

输入格式优化

从标准输入读入数据。
仅一行四个整数 ，变量意义见题目描述。xml

输出格式ci

输出到标准输出。
仅一行一个整数表示答案。博客

样例1输入it

3 2 1 3变量

样例1输出webkit

10方法

题解方法

• dp[i][j]=C(i+j-1,i)=(i+j-1)!/i!(j-1)!

• 复杂度：O(（n+m）log（n+m））

• 可用线性求阶乘逆元优化至O（n+m）

出处：中国计算机学会

此博客为转载文章
非原创

有问题能够在下边提出来记得

@Y_bluefat