组合数 牛顿二项式定理 杨辉三角

二项式定理可以用以下公式表示： 其中，   又有   等记法，称为 二项式系数(binomial coefficient)，即取的 组合数目。此 系数亦可表示为 杨辉三角形。[2]   它们之间是互通的关系。

验证推导

编辑 考虑用 数学归纳法。 当   时，则 假设 二项展开式在   时成立。 设   ，则：   ，（将a、b<乘入）   ，（取出   的项）   ，（设   ）   ，（ 取出   项）   ，（两者相加）   ，（套用帕斯卡法则） 来自百度百科

#include
#include
#include#define N 1001using namespace std;
int C[N][N],n,m;int main()
{scanf("%d%d",&n,&m);if(n<m)swap(n,m);for(int i=0;i<=n;i++) C[i][i]=1,C[i][0]=1;for(int i=2;i<=n;i++)for(int j=1;j<=m;j++)C[i][j]=C[i-1][j]+C[i-1][j-1];printf("%d\n",C[n][m]);
}

组合数计算

 

1137 计算系数

 

2011年NOIP全国联赛提高组

 时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold
题目描述  Description

给定一个多项式(ax + by)^k，请求出多项式展开后x^n y^m项的系数。

输入描述  Input Description

共一行，包含 5 个整数，分别为a，b，k，n，m，每两个整数之间用一个空格隔开。

输出描述  Output Description

输出共 1 行，包含一个整数，表示所求的系数，这个系数可能很大，输出对10007 取模后的结果。

样例输入  Sample Input

1 1 3 1 2

样例输出  Sample Output

3

数据范围及提示  Data Size & Hint

数据范围
对于 30%的数据，有0≤k≤10；
对于 50%的数据，有a = 1，b = 1；
对于 100%的数据，有0≤k≤1,000，0≤n, m≤k，且n + m = k，0≤a，b≤1,000,000。

 

#include
#include
#include#define LL long long
#define N 1010using namespace std;
long long C[N][N];
int s,a,b,k,n,m;long long ksm(long long k,long long tmp)
{long long a=1;long long b=k;while (tmp!=0){if (tmp%2==1) a=(a*b)%10007;b=(b*b)%10007;tmp=tmp/2;}return a;
} int main()
{scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);for (int i=1;i<=k+1;i++) {C[i][i]=1;C[i][1]=1; }for (int i=2;i<=k+1;i++) for (int j=2;j<=i;j++){C[i][j]=(C[i-1][j]+C[i-1][j-1])%10007;}s=C[k+1][m+1];s=(s*(ksm(a,n)*ksm(b,m)))%10007;cout<<s;return 0;
}

P1317

 

 

 poj 1850

Code

Time Limit: 1000MS		Memory Limit: 30000K
Total Submissions: 9918		Accepted: 4749

Description

Transmitting and memorizing information is a task that requires different coding systems for the best use of the available space. A well known system is that one where a number is associated to a character sequence. It is considered that the words are made only of small characters of the English alphabet a,b,c, ..., z (26 characters). From all these words we consider only those whose letters are in lexigraphical order (each character is smaller than the next character). 

The coding system works like this: 
• The words are arranged in the increasing order of their length. 
• The words with the same length are arranged in lexicographical order (the order from the dictionary). 
• We codify these words by their numbering, starting with a, as follows: 
a - 1 
b - 2 
... 
z - 26 
ab - 27 
... 
az - 51 
bc - 52 
... 
vwxyz - 83681 
... 

Specify for a given word if it can be codified according to this coding system. For the affirmative case specify its code. 

Input

The only line contains a word. There are some constraints: 
• The word is maximum 10 letters length 
• The English alphabet has 26 characters. 

Output

The output will contain the code of the given word, or 0 if the word can not be codified.

Sample Input

bf

Sample Output

55

 

题意:

按照字典序的顺序从小写字母 a 开始按顺序给出序列 (序列中都为升序
字符串)
* a - 1
* b - 2
* ...
* z - 26
* ab - 27
* ...
* az - 51
* bc - 52
* ...
* vwxyz - 83681
* 输入字符串由小写字母 a-z 组成字符串为升序，根据字符串输出在字典
里的序列号为多少。

/*
组合数
题意是查一个字串的字典序排名
先求出长度比它小的，显然是ΣC 26 i(i*/
#include
#include
#include#define N 27using namespace std;
int c[N][N],ans;
char str[N];inline void combination()
{for(int i=0;i<=26;i++)  for(int j=0;j<=i;j++)  if(!j || i==j)  c[i][j]=1;  else  c[i][j]=c[i-1][j-1]+c[i-1][j];  c[0][0]=0;  return;  
}int main()
{combination();while(cin>>str){ans=0;int len=strlen(str);for(int i=1;i)if(str[i]<=str[i-1]){cout<<"0"<<endl;return 0;}for(int i=1;i26][i];//长度小于它的所有方案 for(int i=0;i){char ch=(!i)?'a':str[i-1]+1;//比上一个大while(ch//比当前这个小 
            {ans+=c['z'-ch][len-i-1];//长度等于它且排在它前面的所有方案 ch++;}}cout<<++ans<<endl;}return 0;
}

View Code

 

 

codevs 1262

#include
#include
#include#define N 100using namespace std;
int c[N][N],n,ans;int main()
{scanf("%d",&n);for(int i=1;i<=n;i++)for(int j=0;j<=i;j++)if(!j || i==j) c[i][j]=1;else c[i][j]=c[i-1][j]+c[i-1][j-1];printf("%d\n",c[n-1][3]);return 0;
} 

View Code

 

 

瞬间移动

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1422    Accepted Submission(s): 684

Problem Description 有一个无限大的矩形，初始时你在左上角（即第一行第一列），每次你都可以选择一个右下方格子，并瞬移过去（如从下图中的红色格子能直接瞬移到蓝色格子），求到第 n 行第m 列的格子有几种方案，答案对1000000007 取模。

 

Input 多组测试数据。

两个整数 n,m(2≤n,m≤100000)

 

Output 一个整数表示答案

 

Sample Input 4 5

 

Sample Output 10

 

Source 2016"百度之星" - 初赛（Astar Round2B） 

#include
#include
#include#define N 200001
#define M 1000000007
#define ll long longusing namespace std;
ll fac[N]={1,1},inv[N]={1,1},f[N]={1,1};
int n,m;ll C(ll a,ll b)
{return fac[a]*inv[b]%M*inv[a-b]%M;
}int main()
{for(int i=2;i){fac[i]=fac[i-1]*i%M;f[i]=(M-M/i)*f[M%i]%M;inv[i]=inv[i-1]*f[i]%M;}while(~scanf("%d%d",&n,&m)) printf("%lld\n",C(m+n-4,m-2));return 0;
}

View Code

 

 

 

bzoj4517 排列计数

https://www.cnblogs.com/L-Memory/p/9917967.html

 

Luogu P2822组合数问题

https://www.cnblogs.com/L-Memory/p/9918229.html

 

 

转载于:https://www.cnblogs.com/L-Memory/p/7422106.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！