目录

题目-方程的解

在这里插入图片描述

问题分析

因为 k k k, x x x给定, 那么 x x m o d    1000 x ^ x \mod 1000 xxmod1000就可以通过快速幂算法计算出来
假设是 t t t
问题就变成了 a 1 + a 2 + . . . + a k = t a_1 + a_2 + ... + a_k = t a1​+a2​+...+ak​=t的正整数解的个数
隔板法解决
t t t个小球, t − 1 t - 1 t−1的空位, k k k个未知数, 放置 k − 1 k - 1 k−1个隔板, 可以证明方程组的每一个解对应一种隔板的放法, 同时每一种放法对应方程组的一个解
目标就是求 C t − 1 k − 1 C_{t - 1} ^ {k - 1} Ct−1k−1​

算法步骤

  • 快速幂计算 g ( x ) = t g(x) = t g(x)=t
  • 计算组合数 C t − 1 k − 1 C_{t - 1} ^ {k - 1} Ct−1k−1​, 因为没有对数字取模, 需要手写高精度

代码实现

溢出代码

#include <bits/stdc++.h>

using namespace std;

typedef __int128 i128;
typedef long long LL;

const int N = 1010, M = 110;

int k, x;
i128 f[N][M];

int q_pow(int a, int b, int mod) {
   
    int ans = 1;
    a = a % mod;
    while (b) {
   
        if (b & 1) ans = (LL) ans % mod * a % mod;
        a = (LL) a % mod * a % mod;
        b >>= 1;
    }
    return ans;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> k >> x;
    int t = q_pow(x, x, 1000);

    for (int i = 0; i <= t; ++i) {
   
        f[i][0] = 1;
        for (int j = 1; j <= min(i, k); ++j) {
   
            f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
        }
    }

    i128 val = f[t - 1][k - 1];
    vector<int> ans;
    while (val) ans.push_back(val % 10), val /= 10;
    reverse(ans.begin(), ans.end());

    for (int i = 0; i < ans.size(); ++i) cout << ans[i];
    cout << '\n';
    return 0;
}

高精度算法 a c ac ac代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1010, M = 110;

int k, x;
vector<int> f[N][M];

int q_pow(int a, int b, int mod) {
   
    int ans = 1;
    a = a % mod;
    while (b) {
   
        if (b & 1) ans = (LL) ans % mod * a % mod;
        a = (LL) a % mod * a % mod;
        b >>= 1;
    }
    return ans;
}

void set_one(vector<int> &a) {
   
    a.clear();
    a.push_back(1);
}

vector<int> add(vector<int> &a, vector<int> &b) {
   
    if (a.size() < b.size()) return add(b, a);

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

    return ans;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> k >> x;
    int t = q_pow(x, x, 1000);

    for (int i = 0; i <= t; ++i) set_one(f[i][0]);
    for (int i = 1; i <= t; ++i) {
   
        for (int j = 0; j <= min(i, k); ++j) {
   
            f[i][j] = f[i - 1][j];
            if (j > 0) f[i][j] = add(f[i][j], f[i - 1][j - 1]);
        }
    }

    vector<int> ans = f[t - 1][k - 1];
    for (int i = ans.size() - 1; i >= 0; --i) cout << ans[i];

    cout << '\n';
    return 0;
}