思路与算法

按输入顺序先读 $k$、再读 $x$，用二进制快速幂求 $g=x^x\bmod1000$。所有 $a_i$ 都要求为正，先令 $b_i=a_i-1\ge0$，则 $\sum b_i=g-k$。插板法得到有序正整数组数

保证 $k\le g$，且 $g\le999$、$k\le100$。答案没有再取模的要求，可能远大于64位。程序以 $10^9$ 为一段存储大整数，手写逐段相加与进位。用一维Pascal递推求组合数：初始 $dp[0]=1$，逐行更新，列下标从大到小执行 $dp[j]\gets dp[j]+dp[j-1]$，最后输出 $dp[k-1]$。

正确性说明

从 $g$ 个单位中挑选 $k-1$ 个内部切口，得到 $k$ 个非空连续段，其段长恰为一个有序正整数解；任一正整数解也唯一确定这些切口。因此解数为 $\binom{g-1}{k-1}$。

Pascal恒等式 $\binom ij=\binom{i-1}j+\binom{i-1}{j-1}$ 分类考虑一个指定元素是否入选。降序更新保证右侧两项仍来自上一行，归纳得到第 $g-1$ 行目标组合数。逐段加法按基数进位保存精确整数，不发生模截断；快速幂精确得到 $g$，所以打印结果正确。

复杂度

设大整数最多占 $L$ 个基数 $10^9$ 的段。模幂为 $O(\log x)$，初始化 $k$ 个数为 $O(k)$，Pascal更新至多 $O(gk)$ 次，每次加法 $O(L)$，打印 $O(L)$。总时间 $O(\log x+k+gkL)$，额外空间 $O(kL)$；没有保存整个二维Pascal表。

易错点

1. 输入是 $k,x$，方程右边为 $x^x$ 的模1000余数，不是 $x^k$。
2. 变量要求正整数，组合数是 $\binom{g-1}{k-1}$；直接按非负变量计数会多算。
3. 答案精确输出，不对1000取模，不用浮点或64位代替高精度。
4. Pascal列下标必须降序；最高段正常打印，其余段补足9位。给定范围包含 $k=1$，此时唯一解为 $a_1=g$。
5. 覆盖超过64位的 $g=999,k=100$、$k=g$ 以及最大 $x$。独立答案使用任意精度精确组合数，并以小范围正整数组直接枚举核对。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Big {
    static const unsigned BASE = 1000000000;
    vector<unsigned> d;
    Big(unsigned v = 0) : d(1, v) {
    }
    void add(const Big &b) {
        size_t size = max(d.size(), b.d.size());
        d.resize(size);
        ll carry = 0;
        for (size_t i = 0; i < size; i++) {
            ll sum = (ll)d[i] + (i < b.d.size() ? b.d[i] : 0) + carry;
            d[i] = sum % BASE;
            carry = sum / BASE;
        }
        if (carry)
            d.push_back(carry);
    }
    void print() const {
        cout << d.back();
        for (int i = (int)d.size() - 2; i >= 0; i--)
            cout << setw(9) << setfill('0') << d[i];
        cout << '\n';
    }
};
ll power(ll a, ll e) {
    a %= 1000;
    ll result = 1;
    while (e) {
        if (e & 1)
            result = result * a % 1000;
        a = a * a % 1000;
        e >>= 1;
    }
    return result;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int k;
    ll x;
    cin >> k >> x;
    int g = power(x, x);
    vector<Big> dp(k);
    dp[0] = Big(1);
    for (int row = 1; row <= g - 1; row++)
        for (int j = min(row, k - 1); j >= 1; j--)
            dp[j].add(dp[j - 1]);
    dp[k - 1].print();
}