题解【P2822】 组合数问题

Gorun

2019-11-08 20:43:23

题解

组合数问题 题解

1. 在考场上的思路

首先看到这道题，可以使用暴力，具体思路如下。

组合数里面有阶乘，求一个数的阶乘可以使用如下递推公式：

Fact(x)=\begin{cases}x \times Fact(x-1)&x>=1\\1&x=0\end{cases}

再结合组合数公式：

C_n^m=\dfrac{Fact(n)}{Fact(m)\times Fact(n-m)}

可以枚举所有的i,j，一个个验证。

但是这样写有两个问题：

  1. 时间复杂度过高：计算单次Fact(x)所用的时间是O(n)，那么把所有的i,j都枚举出来，最坏的情况就是O(3\times n\times n^2)，必爆无疑。

  2. 精度问题，Fact(x)的增长速度过快，Fact(22)>UnsignedLLong_{max}想算也算不了了（应该没有人会想到高精度吧）

所以我们可以先把前面的C_i^j输出出来看看，结果惊喜地发现：

“这不就是杨辉三角吗？”

当然大神们可以省略以上的分析步骤直接得出杨辉三角的结论。

2. 自己研究时的思路

有了杨辉三角，我们就把原本的阶乘乘除解决了，可以使用递推法，精度问题也不需要担心，毕竟k的值是一定的，我们可以对于每一个递推出来的组合数取模，结果是0个数的即为答案。即：

\\1&j=0\end{cases} $Ans_i^j=Ans_{i-1}^{j}+Ans_{i}^{j-1}-Ans_{i-1}^{j-1}+\begin{cases}0&C_i^j \ne 0\\1&C_i^j =0\end{cases}(j<=i) Ans_i^{j}=Ans_i^i(j=i+1)

其实就是利用了前缀和的思想，不过需要注意的是当j=i+1的情况，按道理来说这个地方应该是没有数的，这里的目的是为了在下一行最后一个递推的时候能够去除越界带来的影响。

附源代码：

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
const int MAXN=2010;
const int MAXT=1010;
int t;
struct Task{
    ll a,b;
}task[MAXT];
ll n,m,k,c[MAXN][MAXN],ans[MAXN][MAXN];
inline void solve()
{
    c[0][0]=1;
    for (ll i=1;i<=2000;i++)
    {
        c[i][0]=1;
        for (ll j=1;j<=i;j++)
        {
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;
            ans[i][j]=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1]+(c[i][j]?0:1);
        }
        ans[i][i+1]=ans[i][i];
    }
}
int main()
{
    scanf("%d%lld",&t,&k);
    solve();
    while (t--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%lld\n",ans[a][min(a,b)]);
    }
}