题目描述

blablabla

样例

blablabla

算法1

(高精度求组合数)

数组方式：将存储组合数的数组多开一维，其中的每一项表示每一位（不能求过大的组合数，否则会爆空间）

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

int k,x;
int f[1010][110][150];//f[i][j][k]表示C[i][j]从低到高的第k位
int qmi(int a,int b,int p)
{
    int res=1;
    while(b)
    {
        if(b&1) res=(ll)res*a%p;
        b>>=1;
        a=(ll)a*a%p;
    }
    return res;
}

void add(int a[150],int b[150],int c[150])//a=b+c
{
    int t=0;//表示进位
    for(int i=0;i<150;i++)//已经确定最大的数不会超过150位
    {
        t+=b[i]+c[i];
        a[i]=t%10;
        t/=10;
    }
}

int main()
{
    cin>>k>>x;
    int n=qmi(x,x,1000)%1000;
    //求C[n-1][k-1](高精度+递推)
    for(int i=0;i<=n-1;i++)
    {
        for(int j=0;j<=i&&j<k;j++)//只需要求到k-1即可，故j<k
        {
            if(j==0) f[i][j][0]=1;
            else add(f[i][j],f[i-1][j],f[i-1][j-1]);
        }
    }
    int it=150;
    while(f[n-1][k-1][it]==0) it--;
    while(it>=0) cout<<f[n-1][k-1][it--];
    return 0;
}

算法2

(高精度求组合数)

分解质因数+高精度乘法 直接求某一组合数的解法

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

int k,x;
bool st[1010];
int primes[1010],cnt;
int sum[1010];//sum[i]表示C[n-1][k-1]中质因数i的个数

void getprimes(int n)//分解质因数
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) primes[++cnt]=i;
        for(int j=1;j<=cnt&&primes[j]<=n/i;j++)
        {
            st[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
}

int get(int a,int x)//求a!中质因数x的个数
{
    int res=0;
    while(a)
    {
        res+=a/x;
        a/=x;
    }
    return res;
}

int qmi(int a,int b,int p)
{
    int res=1;
    while(b)
    {
        if(b&1) res=(ll)res*a%p;
        b>>=1;
        a=(ll)a*a%p;
    }
    return res;
}

vector<int> mul(vector<int> a,int b)
{
    vector<int> c;
    int d=0;
    for(int i=0;i<a.size();i++)
    {
        d+=a[i]*b;
        c.push_back(d%10);
        d/=10;
    }
    while(d) c.push_back(d%10),d/=10;
    return c;
}


int main()
{
    cin>>k>>x;
    int n=qmi(x,x,1000)%1000;
    getprimes(n-1);//求n-1的质因数
    for(int i=1;i<=cnt;i++)
    {
        sum[i]=get(n-1,primes[i])-get(n-k,primes[i])-get(k-1,primes[i]);
    }
    vector<int> ans;
    ans.push_back(1);
    for(int i=1;i<=cnt;i++)
      for(int j=1;j<=sum[i];j++)
        ans=mul(ans,primes[i]);
    for(int i=ans.size()-1;i>=0;i--) cout<<ans[i];
    return 0;
}