组合数的个数
输入一个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 long
using 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;
}
