建設城市（city）（【CCF】NOI Online 能力測試2 入門組第三題 ）
時間限制： 1.0 秒ios
空間限制： 256 MB測試
題目描述
球球是一位建築師。一天，他收到市長的任務：建設城市。球球打算建造 2n 座高樓。爲了保證城市美觀，球球作出了以下計劃：spa
- 球球喜歡整齊的事物。他但願高樓從左向右排成一行，編號依次爲 1∼2n。
- 球球喜歡整數，他要求每座高樓的高度都是正整數。
- 因爲材料限制，高樓的高度沒法超過 m。
- 球球喜歡中間高，兩邊低的造型。他要求前 n 座高樓的高度不降低，後 n 座高樓的高度不上升。
- 球球打算選兩座編號爲 x,y 的高樓做爲這座城市的地標。他認爲只有當這兩座高樓高度相等時，纔會讓城市變得美觀。
球球把本身的想法告訴了市長。市長但願得知全部建設城市的方案數。兩種方案不一樣，當且僅當某座高樓的高度在兩個方案中不一樣。這個問題可難倒了球球。球球找到了你，但願你能幫他算出答案。因爲答案可能很大，你只須要給出答案對 998244353 取模後的結果。.net
輸入格式
從標準輸入讀入數據。code
僅一行四個整數 m,n,x,y，變量意義見題目描述。視頻
輸出格式
輸出到標準輸出。blog
僅一行一個整數表示答案。ci
樣例1輸入
3 2 1 3
樣例1輸出
10
樣例1解釋
全部的方案爲：{1,1,1,1}，{1,2,1,1}，{1,3,1,1}，{2,2,2,1}，{2,2,2,2}，{2,3,2,1}，{2,3,2,2}，{3,3,3,1}，{3,3,3,2}，{3,3,3,3}。get
樣例2輸入
1000 1000 535 1477
樣例2輸出
295916566
思路分析：
1.只在1~4的條件下（先不考慮x,y）若是一塊區域有 n 棟高樓，m 個高度能夠選，則至關於 n個相同的球放入 m 個不一樣的盒子 的方案數,因爲樓的高度能夠相等，則至關於n+m個相同的球放入 m 個不一樣的盒子 的方案數,每一個盒子至少放一球。由插板法可知方案數io
2.再考慮條件5，題目沒有告訴咱們 x,y 是否在 n 的兩側，因此要分狀況討論
(1)case1:x≤n<y
枚舉 x,y的高度。假設當前 x,y的高度爲 i，則：
- x 左邊的 x-1個高樓高度範圍爲 [1,i]。
- x 右邊 n 左邊（包含 nn）的 n-x個高樓高度範圍爲 [i,m]。
- n 右邊（不包含 n）y左邊的 y−n−1 個高樓高度範圍爲 [i,m]。
- y 右邊的 2n-y個高樓高度範圍爲 [1,i]。
根據乘法原理，將以上四種狀況相乘便可。
(2)Case 2：y≤n 或 x,y>n。
將 [x,y] 中間的高樓當作一個高樓，則至關於
#include<iostream>
using namespace std;
const int mod=998244353;
int m,n,x,y;
long long int ans=0;
int inverse(int x,int mod) {
int power=mod-2;
x %= mod;
int num = 1;
for (; power; power >>= 1, (x *= x) %= mod)
if(power & 1) (num *= x) %= mod;
return num;
}
int cn(int a,int b)//組合數計算
{
int sum=1;
for(int i=1;i<=b;i++)
{
sum=sum*(a-b+i)%mod;
sum=sum*inverse(i,mod)%mod;//求i模mod的逆元
}
return sum;
}
int main()
{
cin>>m>>n>>x>>y;
if(x<=n&&y>=n)//case1狀況
{
for(int i=1;i<=m;i++)
ans+=cn(x+i-1,i-1)*cn(n-x+m-i,m-i)*cn(y-n+m-i,m-i)*cn(2*n-y+i-1,i-1)%mod;
cout<<ans;
}
else
{
ans=cn(n+m-1,m-1)*cn(n+m-1-x+y,m-1)%mod;
cout<<ans;
}
return 0;
}