组合知识

 

从m个物品里选出n个的方案数,记作CnmCmn,即为组合数
组合数有很多很多的性质和定理。。。
注意由于本人沉迷玩梗无法自拔,如果看见您看不懂的梗请随意跳过。

组合数通项公式
Cnm=m!n!∗(m−n)!
Cmn=m!n!∗(m−n)!

证明:现在我们从m个不同的数里选出n个数组成一个排列,第一个位子上的数有m种取法,第二个位子上的有m-1种,第三个位子上有m-2种。。。共有m!(m−n)!m!(m−n)!种
然而,我们对于顺序没有要求,假设取出了n个数,第一个位子上有n种放法,第二个位子上有n-1种。。。所以我们刚才得到的哪个东西还要除一个n!n!
组合数递推公式
Cnm=Cnm−1+Cn−1m−1
Cmn=Cm−1n+Cm−1n−1

证明:从m个不同的数中取n个,第m个数如果取的话有Cn−1m−1Cm−1n−1种取法,如果不取则有Cnm−1Cm−1n种。
如果您是组合数新手,请牢记以上两个公式
性质1
Cnm=Cm−nm
Cmn=Cmm−n

证明:显然从m个物品里选n个和从m个物品里选m-n个丢掉的方案数是一样的。
性质2
Crm+r+1=∑i=0rCim+i
Cm+r+1r=∑i=0rCm+ii

证明:用组合数的递推公式。
首先C0m=C0m+1=1Cm0=Cm+10=1
C0m+C1m+1+C2m+2+…+Crm+rCm0+Cm+11+Cm+22+…+Cm+rr=
C1m+C1m+1+C2m+2+…+Crm+rCm1+Cm+11+Cm+22+…+Cm+rr=
C1m+2+C2m+2+…+Crm+rCm+21+Cm+22+…+Cm+rr=
Crm+r+1Cm+r+1r
性质3
Cnm∗Crn=Crm∗Cn−rm−r
Cmn∗Cnr=Cmr∗Cm−rn−r

证明:用组合数的通项公式
Cnm∗Crn=Cmn∗Cnr=
m!n!(m−n)!∗n!r!(n−r)!=m!n!(m−n)!∗n!r!(n−r)!=
m!r!(m−r)!∗(m−r)!(m−n)!(n−r)!=m!r!(m−r)!∗(m−r)!(m−n)!(n−r)!=
Crm∗Cn−rm−rCmr∗Cm−rn−r
性质4(二项式定理)
∑i=0mCim=2m
∑i=0mCmi=2m

证明:显然CimCmi代表一个m位二进制数有i个0的情况下的数量,那么这个和就是m位二进制数的数量了。
推广一下这个二项式定理:
∑i=0mCim∗xi=(x+1)m
∑i=0mCmi∗xi=(x+1)m

这个又怎么证明呢?先把(x+1)m(x+1)m写成(x+1)(x+1)(x+1)…(x+1)(x+1)(x+1)…的格式,然后每一项很精妙啊,比如说i次方项,选的ii个xx是从哪个括号里来呢?有CimCmi种方案吧,所以xixi项的系数是CimCmi。
这就是杨辉三角的应用(可以自行百度)
性质5
C0m−C1m+C2m−…±Cmm=0
Cm0−Cm1+Cm2−…±Cmm=0

证明:假如m是奇数的花,由性质1可知正确。
假如m是偶数的花,这个里面的花,用一下递推公式,然后显然C0m−1=C0m=1Cm−10=Cm0=1并且Cm−1m−1=Cmm=1Cm−1m−1=Cmm=1,则:
C0m−C1m+C2m−…+Cmm=Cm0−Cm1+Cm2−…+Cmm=
C0m−1−C0m−1−C1m−1+C1m−1+C2m−1−…+Cm−1m−1=0Cm−10−Cm−10−Cm−11+Cm−11+Cm−12−…+Cm−1m−1=0
性质6
C0m+C2m+C4m…=C1m+C3m+C5m+…=2m−1
Cm0+Cm2+Cm4…=Cm1+Cm3+Cm5+…=2m−1

证明:这个根据性质4和性质5可知正确。
性质7
Crm+n=C0m∗Crn+C1m∗Cr−1n+…+Crm∗C0n
Cm+nr=Cm0∗Cnr+Cm1∗Cnr−1+…+Cmr∗Cn0

证明:很简单,考虑我选出的r个物品在前m个物品有几个,在后n个物品里有几个即可。
特别的:
Cnm+n=C0m∗C0n+C1m∗C1n+…+Cmm∗Cmn
Cm+nn=Cm0∗Cn0+Cm1∗Cn1+…+Cmm∗Cnm

这个是根据性质1变形得到的。
性质8
n∗Cnm=m∗Cn−1m−1
n∗Cmn=m∗Cm−1n−1

证明:运用通项公式
n∗Cnm=n∗Cmn=
n∗m!n!(m−n)!=n∗m!n!(m−n)!=
m!(n−1)!(m−n)!=m!(n−1)!(m−n)!=
m∗(m−1)!(n−1)!(m−n)!=m∗Cn−1m−1m∗(m−1)!(n−1)!(m−n)!=m∗Cm−1n−1
性质9
∑i=1nCin∗i=n∗2n−1
∑i=1nCni∗i=n∗2n−1

证明:用通项公式
∑ni=1Cin∗i=n∗2n−1=∑i=1nCni∗i=n∗2n−1=
∑ni=1n!(i−1)!(n−i)!=∑i=1nn!(i−1)!(n−i)!=
(∑ni=1(n−1)!(i−1)!(n−i)!)∗n=(∑i=1n(n−1)!(i−1)!(n−i)!)∗n=
(∑n−1i=0Cin)∗n=(∑i=0n−1Cni)∗n=
现在看性质4。
n∗2n−1n∗2n−1
性质10
∑i=1nCin∗i2=n∗(n+1)∗2n−2
∑i=1nCni∗i2=n∗(n+1)∗2n−2

证明:
和上一个性质有些类似。
∑ni=1Cin∗i2=∑i=1nCni∗i2=
用和上面差不多的方法得到:
(∑n−1i=0Cin−1∗(i+1))∗n=(∑i=0n−1Cn−1i∗(i+1))∗n=
(∑n−1i=0Cin−1∗i+∑n−1i=0Cin−1)∗n=(∑i=0n−1Cn−1i∗i+∑i=0n−1Cn−1i)∗n=
用性质9和性质4可以得到:
(2n−2∗(n−1)+2n−1)∗n=(2n−2∗(n−1)+2n−1)∗n=
很明显2n−1=2∗2n−22n−1=2∗2n−2
所以原式=2n−2∗(n+1)∗n2n−2∗(n+1)∗n
性质11
∑i=0n(Cin)2=Cn2n
∑i=0n(Cni)2=C2nn

证明:boshi说,他的门前有两棵树,一棵是枣树,另一棵也是枣树,每棵树上有n个枣子,每个枣子都有一个不同的神奇的膜法符号。现在boshi从两棵树上一共打下了n个枣子,那么一共有多少种方案?是Cn2nC2nn,也是第一棵树上打下i个枣子,从第二棵树上打下(n-i)棵枣子的方案,根据乘法原理乘起来,又因为Cin=Cn−inCni=Cnn−i,所以得到上一个式子。
卢卡斯定理
简单的说就是求Cnm%pCmn%p的时候可以化作Cnm=Cn/pm/p∗Cn%pm%pCmn=Cm/pn/p∗Cm%pn%p,那么只要递归Cn/pm/pCm/pn/p即可。
证明我蠢我不会自己想

后记
啊啊啊搞了一下午终于证完了累死了。。。感觉自己和组合数的感情有了明显的提升(才怪)。。。
在文章的最后%一发数王。。。
%%%%%%%%%数王您太强了%%%%%%%%%%%
数王说以上所有定理都可以用那个那个那个证,虽然我不知道那个是哪个,但是反正好强啊%%%%%%%%
好吧以上都是不正经内容,正经内容是:
在做题的时候大家可能不一定都会遇到这些性质,但是在手动证明完这些性质后对于组合数变形的问题就会有更深一层的理解,总之,组合数性质可以用一下方法推出:
1.情景假设法(假设boshi从枣树选枣子的方案。。。)
2.隔板法(boshi把枣子放成一排,通过在枣子间添加隔板来分组。。。)
3.通向公式法
4.递推公式法

转载自https://blog.csdn.net/litble/article/details/75913032

暴力出奇迹

题目描述

给出多个整数n,要求求出a,b,c字典序最小的 a2+b2+c2=n

输入

一个整数t,表明数据组数 (t <= 10)
接下来t行,每行一个整数n (1 <= n <= 10000)

输出

三个整数 a,b,c
如果无解,输出”???”

样例输入

2
7
30

样例输出

???
1 2 5

来源/分类

2018新生赛 八

#include<cstdio>
int main()
{
	//freopen("in.txt","r",stdin);
	int t;
	scanf("%d",&t);
	while(t--){
		int n,flag=0;
		scanf("%d",&n);
		int i=0,j=0,k=0;
		for(i=0;i*i+j*j+k*k<=n;i++){
			for(j=i;i*i+j*j+k*k<=n;j++){
				for(k=j;i*i+j*j+k*k<=n;k++){
					//printf("%d %d %d",i,j,k);
					if(i*i+j*j+k*k==n){
							flag=1;
							break;
					}
				}
				if(flag) break;
				k=j;//若不还原,则可能开始下一次循环时循环的判断条件提前为假 
			}
			if(flag) break;
			j=i;
		}
		if(flag) printf("%d %d %d\n",i,j,k);
		else printf("???\n");
	}
}

 

大数减法

这里我们来看看大数减法,思想不是很难,看了代码你就知道了。

主要思想:把每一位相减,减完之后从低位判断是否小于0,若小于0向前一位借一,前一位减一即可。

下面是代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
const int Max=10005;
string m,n;
int c[Max],d[Max],sum[Max];
int main()
{
	cin>>m>>n; 
	memset(c,0,sizeof(c));
	memset(d,0,sizeof(d));
	memset(sum,0,sizeof(sum));
	int len1=m.size(),len2=n.size();
		for(int i=len1-1,j=0;i>=0;i--,j++)
			c[j]=m[i]-48;
		for(int i=len2-1,j=0;i>=0;i--,j++)
			d[j]=n[i]-48;
		int len=max(len1,len2);
		for(int i=0;i<len;i++){
			sum[i]=c[i]-d[i];
			for(int i=0;i<len;i++)
				if(sum[i]<0){ //判断正负
					while(c[i]<0){
						c[i+1]-=1;
						c[i]+=10;
					}
				}
			for(int i=len-1;!sum[i];i--) len--;
			for(int i=len-1;i>=0;i--)
				printf("%d",sum[i]);
		}
}