首页 > 代码库 > Uva 11076 Add Again （数论+组合数学）

Uva 11076 Add Again （数论+组合数学）

2024-08-26 15:39:10   217人阅读

题意：给你N个数，求把他们的全排列加和为多少

思路：对于这道题，假设数字k1在第一位，然后求出剩下N-1位的排列数num1，我们就可以知道k1在第一位时的排列有多少种为kind1，

         同理，假设数字k2在第一位然后求出剩下N-1位的排列数num2，我们就可以知道k2在第一位时的排列有多少种为kind2，

         k1*num1+k1*num2.....+kn*numn 就是我们要求的这些数对第一位的所有贡献，我们知道第一位的贡献=对第二位的贡献=第三位的贡献.....

         把所有贡献加和，就能求出结果

知识:

 1、 如何求重复数的全排列

         元素表述：   a1,a1,...a1,   a2,a2,...a2,.......,an,an,...an 
         其中，a1的个数为N1,   a2的个数为N2,以此类推，总个数为M。 

         则可以证明不重复的排列种类的数目:   M!/(N1!*N2!*...*Nn!) 

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#define ull unsigned long long
using namespace std;

ull C[15][15];

void get_C()
{
    memset(C,0,sizeof(C));
    C[1][0]=1;
    C[1][1]=1;
    for(int i=2;i<=12;i++)
    {
        for(int j=0;j<=i;j++)
        {
            C[i][j]=C[i-1][j]+C[i-1][j-1];
        }
    }
}


int main()
{
    int n;
    int data[15];
    int num[10];
    get_C();
    while(cin>>n&&n)
    {
        memset(num,0,sizeof(num));
        for(int i=0;i<n;i++)
        {
            cin>>data[i];
            num[data[i]]++;
        }
        ull ans=0;
        for(int i=0;i<=9;i++)
        {
            ull k=0;
            if(num[i])
            {
                k=1;
                int m=n-1;
                num[i]--;
                for(int j=0;j<=9;j++)
                {
                    if(num[j]==0) continue;
                    k=k*C[m][num[j]];
                    m=m-num[j];
                    //cout<<k<<endl;
                }
                num[i]++;

            }
            ans=ans+i*k;
        }
        ull sum=0;
        for(int i=0;i<n;i++)
           sum=sum*10+ans;
        cout<<sum<<endl;
    }
    return 0;
}

 

Uva 11076 Add Again （数论+组合数学）


联系
我们