题解 P6475 【[NOI Online #2 入门组]建设城市】

· · 题解

题面传送门。

前置知识:组合数学(P3811 【模板】乘法逆元,利用乘法逆元求组合数)。

题目没有告诉我们 x,y 是否是在 n 的两侧,所以要分情况讨论。

```cpp #include <bits/stdc++.h> #define ll long long using namespace std; const int N=2e5+5; const int p=998244353; ll ksm(ll a,ll b){ll s=1,m=a; while(b){if(b&1)s=s*m%p; m=m*m%p,b>>=1;} return s;} ll m,n,x,y,ans,fc[N],ifc[N]; ll C(ll m,ll n){return fc[n+m-1]*ifc[n]%p*ifc[m-1]%p;} int main(){ cin>>m>>n>>x>>y; fc[0]=1; for(int i=1;i<=m+n;i++)fc[i]=fc[i-1]*i%p; ifc[m+n]=ksm(fc[m+n],p-2); for(int i=m+n-1;~i;i--)ifc[i]=ifc[i+1]*(i+1)%p; if(x<=n&&y>n)for(int i=1;i<=m;i++)ans=(ans+C(i,x-1)*C(m-i+1,n-x)%p*C(m-i+1,y-n-1)%p*C(i,2*n-y))%p; else ans=C(m,n)*C(m,n+x-y)%p; cout<<ans<<endl; return 0; } ``` 写的比较匆忙,如有笔误还请尽快指出,感激不尽! Upd on 2020.5.3:修改部分文字和代码。