分析

• 对于$x^x \ mod \ 1000$，可以使用快速幂求解，假设结果为n。

• 剩下的问题变成将n分成k个数，且每个数必须大于0，问有多少种方法？可以使用隔板法，这种方法很常用。

• 相当于一共n个小球排成一排，然后在n-1个空挡中插入k-1个隔板（每个空挡最多插入一个隔板），有多少种方式？

• 答案是组合数：$C_{n-1}^{k-1}$，可以参考各种不同数据范围的组合数求解方法，因为这里数据比较小，可以直接使用递推法求解即可。

• 还需要估计一下本题最大的值为多少，最大为：

$$ C_{1000}^{100} = \frac{1000!}{100! \times 900!} $$

• 因为数据过大，因此这里使用数组记录结果，数组长度开到150完全足以。

代码

#include <iostream>

using namespace std;

const int N = 150;  // 每个组合数不会超过150位

int k, x;
int f[1000][100][N];  // f[i][j]表示组合数C(i, j)

int qmi(int a, int k, int p) {

    int res = 1 % p;
    while (k) {
        if (k & 1) res = (res * a) % p;
        a = (a * a) % p;
        k >>= 1;
    }
    return res;
}

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

int main() {

    cin >> k >> x;

    int n = qmi(x % 1000, 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]);

    // 输出结果, g[0]代表最低位
    int *g = f[n - 1][k - 1];
    int i = N - 1;
    while (!g[i]) i--;
    while (i >= 0) cout << g[i--];

    return 0;
}