$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

1. 用快速幂求出 n = x ^ x % 1000
2. 常用公式：C[a][b] = C[a - 1][b] + C[a - 1][b - 1]
3. a[1] + a[2] + ... + a[k] = n，用隔板法可知共 C[n - 1][k - 1] 种方案
4. 用高精度加法求出 C[n - 1][k - 1] 并将其输出

完整代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 150;

int k,x;
int f[1000][100][N];

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

void add(int c[],int a[],int b[])
{
    for(int i=0,t=0;i<N-1;i++)
    {
        t+=a[i]+b[i];
        c[i]=t%10;
        t/=10;
    }
}

int main()
{
    cin>>k>>x;

    int n=qmi(x,x,1000); //n = x ^ x % 1000

    //计算 C[n - 1][k - 1]
    for(int i=0;i<n;i++)
        for(int j=0;j<=i&&j<k;j++)
            if(!j) f[i][j][0]=1;
            else add(f[i][j],f[i-1][j],f[i-1][j-1]);

    //输出 C[n - 1][k - 1]
    int i=N-1;
    while(!f[n-1][k-1][i]) i--;
    while(i>=0) cout<<f[n-1][k-1][i--];

    return 0;
}