首页 > 代码库 > 组合数学 - 组合数的个数
组合数学 - 组合数的个数
组合数的个数
输入一个n,然后输入n个一位数，求这n个数组成的不重复出现的整数的总和。
Mean:
略
analyse:
这样的数可以是1~n位，总共数的数目为：P(n,1)+p(n,2)+p(n,3)+.....+p(n,n)个。(其中p(n,m)表示从n个数中选m个数组成的排列的数目)。
若将这些数全部罗列出来再来求和，这不是一个好办法。其实我们可以将个位的和a1求出来，然后十位的和a2求出来，然后百位，然后千位......直到第n-1位。
那么最后的和就是：
sum=a1*1+a2*10^1+a3*10^2+a4*10^3.....an-1*10*n-2;
具体参看《组合数学.第三版》：P13
Time complexity：O(n^2)
Source code：
//Memory Time// 1347K 0MS// by : Snarl_jsb#include<algorithm>#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<vector>#include<queue>#include<stack>#include<map>#include<string>#include<climits>#include<cmath>#define N 100010#define LL long longusing namespace std;LL n,sum,t;LL a[5];LL buff(LL s,LL e){ LL res=1; for(LL i=s;i>=e;--i) { res*=i; } return res;}LL combination(LL n,LL m){ LL t1=buff(n,n-m+1); return t1;}int main(){// freopen("C:\\Users\\ASUS\\Desktop\\cin.txt","r",stdin);// freopen("C:\\Users\\ASUS\\Desktop\\cout.txt","w",stdout); while(~scanf("%I64d",&n)) { sum=0; for(int i=1;i<=n;++i) { scanf("%I64d",&t); sum+=t; } LL tmp=1; a[0]=1; for(int i=1;i<n;i++) { a[i]=combination(n-1,i); } LL carry=1; LL ans=0; for(int i=0;i<n;++i) { LL tmp=0; for(int j=i;j<n;++j) { tmp+=a[j]; } ans+=tmp*carry*sum; carry*=10; }// for(int i=0;i<n;i++)// cout<<a[i]<<endl; printf("%I64d\n",ans); } return 0;}
组合数学 - 组合数的个数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。