CF630G 题解

· · 题解

前言

这道题算是一道入门的组合数学题，难度不大，适合刚学组合数学的同学写。其实主要的几种思路其他题解已经说的比较清楚了，这篇题解除了会对题目进行讲解以外还会再补充一些其他与组合数学入门的内容。

正文

这道题的题意很简单：给定 5 面红旗， 3 面蓝旗以及 n 张桌子，要求这 8 面旗必须全部放完，其中桌子上可以选择不放旗。求合法的方案数。

这道题读完之后很容易想到用组合数来解决该题，那么具体应该如何解决呢？

分析题意可提取如下几个关键点：

  1. “当所有的旗分配完后，在某一张桌子上红旗，蓝旗，红旗与红旗，红旗，蓝旗这样类似的不记为不同种”，也就是旗的顺序对这道题并没有影响。
  2. 一张桌子上可以放红旗和多张蓝旗。
  3. 题中的红旗与蓝旗是互不干扰的。

第一点和第二点暗示了这道题其实就是可重复组合，所以可以使用公 C_{n+m-1}^{m} 来计算答案。第三点暗示了我们可以把蓝旗和红旗分开处理，因为二者是互不干扰的，所以我们可以分别计算出红旗对答案的贡献以及蓝旗对答案的贡献，并最后根据乘法原理将二者相乘以得到答案。

对于红旗，桌子有 n 张，红旗有 5 张，可以直接套入公式得到 C_{n+4}^{5}。蓝旗同理，套公式得 C_{n+2}^{3}。

则最终答案为 C_{n+4}^{5} \times C_{n+2}^{3}。

那么现在我们已经知道答案是什么了，接下来要做的就是如何得到答案。

我们现在要做的只有求出组合数 C 即可，因为只要得到了 C，那么我们就可以直接得到答案。而求出 C 的方法主要有四种：

  1. 暴力模拟出 C 的公式，以得到答案。
  2. 预处理出求出 C 需要的相关内容后再求出 C。
  3. 用递推的方式求出 C。
  4. 用卢卡斯定理求出 C（这种方法适用于 n、m 比较大，但模数较小的情况）。

由于本题 n 的范围较小，所以可以三种方法都可以通过本题，其中第二种是最常用的。由于并没有人用递推的方式求出 C（又慢又麻烦当然没人用啦），这个做法的时间复杂度是 O{(n^{2})} 的，并不是很常用（由于大多数组合数学的题目都是单次查询且数据范围都较大，所以这种方法并不常用）。不过这个方法相较于其他几种方法，该方法有着码量小，写的时候较方便等优点，并且非常适合数据范围较小，但是是多次查询的题目，这里我说一下用递推的方式求出 C。

组合数的递推式是 C_{n}^{m}=C_{n-1}^{m}+C_{n-1}^{m-1}，也就是所谓的“杨辉三角”，这个递推式大家在初学组合数的时候应该都知道，并且它很好证明，这里不再赘述。实现用递推式的方法求出 C 的主要途径也有两种，一种是用类似 DP 的方法对其进行状态转移，另一种是用递推的方式去实现。但是呢由于我们已经提前算出答案了，我们发现第二项的值是固定的且非常小，所以我们这里讲一下用第一种方法来实现这道题。求出 C 的方法是：定义一个二维数组 C，其中 C_{n,m} 表示 C_{n}^{m} 的大小，我们根据递推式就可以以 O{(n^{2})} 的时间复杂度预处理出这个数组。

CODE

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<cassert>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<cstdlib>
using namespace std;
#define ll long long
#define ull unsigned long long
#define int ll
int read()
{
    int now=0,nev=1;
    char c=getchar();
    while(c<'0' || c>'9')
    {
        if(c=='-')
            nev=-1;
        c=getchar();
    }
    while(c>='0' && c<='9')
    {
        now=(now<<1)+(now<<3)+(c&15);
        c=getchar();
    }
    return now*nev;
}
const int MAXN=510;
int n;
int C[MAXN][MAXN];
void get_C()
{
    for(int i=0;i<=n+4;i++)//最多用到 n+4，且这题是单次询问，所以 i 只要循环到 n+4 就够了 
    {
        for(int j=0;j<=i && j<=5;j++)//最多用到 5，所以这题 j 只要循环到 5 就够了 
        {
            if(j==0)
                C[i][j]=1;
            else
                C[i][j]=C[i-1][j]+C[i-1][j-1];
        }
    }
}
signed main()
{
    n=read();
    get_C();
    printf("%lld",C[n+4][5]*C[n+2][3]);
    return 0;
}

结尾

此题很适合刚学组合数的同学入门（为什么我到现在了才知道这道题....），希望这篇题解能对大家有帮助。