【组合数学入门+例题】

2019/07/26 11:14
阅读数 38

前言

组合数学是数论的一部分,应该算是入门,但是卡常的组合数题目真的是毒瘤

简介

(摘自知乎)

**组合数学(Combinatorics)**是纯数学的一个分支,主要研究离散、有限或可数的数学结构。 除了纯数学,组合数学在应用数学、理论物理、计算机科学等分支也有着很多应用。在计算机科学中,组合数学又被称作 “离散数学”。 在美国数学会的学科分类中,组合数学下设五个子学科,分别为:计数组合、设计理论、图论、极值组合、代数组合。

基础知识点:组合数

从$n$个不同元素中,任取$m(m≤n)$个元素并成一组,叫做从$n$个不同元素中取出$m$个元素的一个组合;从$n$个不同元素中取出$m(m≤n)$个元素的所有组合的个数,叫做从$n$个不同元素中取出$m$个元素的组合数。 我们通常用$C^n_m$来表示上面这种情况。 基础计算公式: $C^n_m=\frac{m!}{n!(m-n)!}$

例题部分

1.[HNOI2008]越狱 2.SAC#1 - 组合数 3.妖梦拼木棒 ($luogu$上都能搜到)

重点讲讲第二个 题目的意思是: 给定一个n,求$\begin{matrix} \sum_{i=1}^N C(n,i) \end{matrix}$,这里的$C(n,i)$表示在n件物品里无序选取i件的组合数,当然,题目限制i必须是偶数。 首先: $C_n^0+C_n^1+C_n^2+...+C_n^n=2^n$ 这个应该不难理解,可以理解为每件物品都有选或者不选,件数不限,所以可以用$2^n$表示总和。 其次: $C_n^0-C_n^1+C_n^2-C_n^3+(-1)^nC_n^n=0$ 根据上面那个式子就可以得到这个。最后一项的符号根据n来确定。 所以: $C_n^0+C_n^2+C_n^4+...=C_n^1+C_n^3+C_n^5+...=2^{n-1}$ 第二个式子就告诉我们,正数项和负数项的数值和是相同的,所以总和是0,第一个式子也可以得出这两个相同值的式子的和是2^n,所以它们各自值的绝对值就是$2^{n-1}$. 所以,题目中所求的,用快速幂就可以很快求出来... 代码:

#include<bits/stdc++.h>
using namespace std;
long long qpow(long long a,long long b,long long p)
{
	long long x=a;
	long long ans=1;
	while(b)
	{
		if(b&1)
			ans*=x;
		ans%=p;
		(x*=x)%=p;
		b>>=1;
	}
	return ans;
}
int main()
{
	long long a,b,p;
	cin>>b;
	cout<<qpow(2,b-1,6662333)<<endl;
	return 0;
}

另外两道题目讲讲思路吧: 1.越狱这道题一样用推导公式,首先算出所有犯人加在一起的所有状态,减去所有相邻房间的犯人的宗教不相同的情况,即为答案。 3.木棍长度最长才5k,外层枚举有两根的长度的木棍,然后内层循环找另外两根更短的能够组成第三边的,找到了就方案数++. ov. 摸鱼酱.

展开阅读全文
sac
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部