组合数问题

引言

这道题是昨天蓝桥杯校赛出的一道题，然后自己没做出来，主要是没想到，在回去的路上，听到有同学在议论这道题，我故意上前听了一下，当我听到C(m,n)的时候我一下子恍然大悟，心想这不就是组合问题吗，确实当时剩了最后一小时了一道题都没做出来，还是最后一小时的时候才做出来两道，确实是自己练得不够啊，继续加油吧，先复盘这道题。

一、题目描述

在大学四年的学习中，修满学分是必须要求，我校大多数专业的学分要求为166分，在四年中，通识必修课、实验课、实践课总分大约为158分，剩下8分往往需要
同学们学习选修课程。现在有1分的选修课16门（每门课不一样），0.5分的选修课18门（每门课不一样），通过计算，我们想知道有多少种正好修满8分的选课
方式（不同的选修课就是不同的选课方式）。输出一行一个答案，该题只有一个测试点。
程序类似于
#include<bits/stdc++.h>
using namespace std;
int main(){
printf("123456");
return 
}

输入描述:
无
输出描述:
无
备注:
无

二、题目思路

这道题最初想的是用那个递归做，就是之前也发过博客链接: 指数型枚举想着拿指数型枚举做，想着不就是34个课，然后前16个加1分后18个加0.5分，然后就是一个该课选或者不选的问题嘛，然后就用这种思路一直做，然后就当然的一直超时，我就想会不会是自己的dfs写的有问题呢，就一直改一直改，就这样时间就被浪费了，然后再回过头来做这道题时，用那个位运算做的（还是那篇博客指数型枚举的第二种写法），想着dfs写不对，这个位运算总能写对吧，然后就做，发现还是超时，那我就想可能是2 ^ 34太大了，其实当时第一眼看的时候我就知道感觉有问题，但自己不知道2 ^ 34到底多大，所以就一直没管，刚才拿计算器一案发现有170亿，天啊这肯定超时啊，一般复杂度控制在10 ^ 7 ~ 10 ^ 8是最佳的，就是一百万到一千万，有时你的程序能再小的话一个亿有时也能勉强过，然后我就觉得这肯定不是我的问题了，就是有某种数学公式能做，当时是这么个想法，然后就一直想数学公式，当然这种东西你第一下想不出基本是想不到的了，然后自己就在那一个个试，然后就结束了。
言归正传这就是一个组合数的问题就是求在16个里选0 ~ 8和18个里选0 ~ 16个

三、代码实现

#include <iostream>

using namespace std;

typedef long long LL;

LL f(int n)  //n!
{
    LL res = 1;
    for(int i = 1; i <= n; ++i) res *= i;
    
    return res;
}

LL fun(int m, int n)  //c(m,n)
{
    return f(n)/(f(m)*f(n-m));
}

int main()
{
    LL res = 0;
    for(int i = 0; i <= 8; ++i)
    {
        res += fun(8-i,16)*fun(2*i,18);
    }
    
    cout << res;
    
    return 0;
}