题解 P6475 【[NOI Online #2 入门组]建设城市（民间数据）】

· · 题解

如果公式挂了请私信我并到博客查看

前言：

这个人网络爆炸了，于是pj成功爆了0。可恶的土豆服务器(〃＞皿＜)

由于半年没写过关于组合数的题了，所以有锅别怪我（

正文开始

前置知识：快速幂，组合数学（初赛时有讲），逆元。

首先我们设一个函数f(i,j)表示值域为1+x \sim j+x|x\in N（可以证明不管x为多少都对答案没有多大关系），序列长度为i的序列的排列方案。

然后由插板法可得

f(i,j)=\dbinom{i+j-1}{j-1}

接下来就开始狂废脑子了……

对于答案的统计，需要分情况讨论

对于这种情况我们可以做一个图示：

在此时，这个序列便分为四个区间：1\sim x-1,x+1\sim n,n+1\sim y-1,y+1\sim n*2

通过枚举m以及乘法原理，我们可以得到这种情况的答案：

ans=\sum\limits_{i=1}^m f(x-1,i)*f(n-x,m-i+1)*f(y-n-1,m-i+1)*f(2*n-y,i)

图示：

注意到x与y是相等的，所以我们可以把区间x\sim y合并成一个点。

又根据乘法原理，我们可以O(1)计算出答案：

ans=f(n,m)*f(n+x-y,m)

完了？完了。

似乎忘了什么……

对了：

如何O(1)计算f函数啊!!!∑(ﾟДﾟノ)ノ

我们之前提到过f(i,j)就是\dbinom{i+j-1}{j-1}

所以求f函数又转化为求组合数

而众所周知，

\dbinom{n}{m}=\dfrac{n!}{m!(n-m)!}

所以

f(i,j)=\dfrac{(i+j-1)!}{i!(j-1)!}

我们现在剩下的任务就是求1!\sim 200000!的逆元（n+m最大为200000，当然你也可以只预处理到n+m）。

实在不知道逆元的到这来

接下来介绍两种求逆元的方法：

学过都知道，一个数x的逆元就是x^{mod-2}（不会的记得这个公式就行了）

所以在循环的时候，直接每次利用求出的fra数组（也就是阶乘）以及快速幂进行求逆元就行了

时间复杂度\Theta(nlogn)

代码

void prework()
{
    fac[0]=inv[0]=1;
    for(int i=1;i<=200000;i++)fac[i]=(fac[i-1]*i)%mod;
    for(int i=1;i<=200000;i++)inv[i]=quick(fac[i],mod-2);
}

首先我们还需要求出fra数组。

然后求出inv[n+m]。

最后后从后往前循环，每次求inv[i]（阶乘逆元）时，将inv[i+1]乘以(i+1)即可得到inv[i]。

证明？

(n+1)! * \dfrac{1}{n+1}=n!

时间复杂度为\Theta(n)

代码

void prework()
{
    fac[0]=inv[0]=1;
    for(int i=1;i<=200000;i++)fac[i]=(fac[i-1]*i)%mod;
    inv[200000]=quick(fac[200000],mod-2);
    for(int i=199999;i;i--)inv[i]=inv[i+1]*(i+1)%mod;
}

然后调用f数组时的代码：

ll f(int n,int m){return fac[n+m-1]*inv[n]%mod*inv[m-1]%mod;}

Final Code

#include<iostream>
#include<cstdio>
#define mod 998244353
#define ll long long
using namespace std;
ll fac[200001],inv[200001],n,m,x,y,ans;
ll quick(ll a,ll b)
{
    ll xx=a,yy=1;
    while(b)
    {
        if(b&1) yy=yy*xx%mod;
        xx=xx*xx%mod;
        b/=2;
    }
    return yy;
}
ll f(int nn,int mm){return fac[mm+nn-1]*inv[nn]%mod*inv[mm-1]%mod;}
int main()
{
    fac[0]=inv[0]=1;
    for(int i=1;i<=200000;i++)fac[i]=(fac[i-1]*i)%mod;
    inv[200000]=quick(fac[200000],mod-2);
    for(int i=199999;i;i--)inv[i]=inv[i+1]*(i+1)%mod;
    cin>>m>>n>>x>>y;
    if(x<=n&&y>n)
        for(int i=1;i<=m;i++)
            ans=(ans+f(x-1,i)*f(n-x,m-i+1)%mod*f(2*n-y,i)%mod*f(y-n-1,m-i+1))%mod;
    else ans=f(n,m)*f(n+x-y,m)%mod;
    cout<<ans;
}