题解 P1771 【方程的解_NOI导刊2010提高（01）】

· · 题解

首先呢，g(x)我们是可以求解的，我们设n=g(x)
我们可以先写出n个1，我们发现它们之间有n-1个空隙，而我们的任务是寻找k个数，使k个数的和等于n，于是我们就可以将问题转化成在n-1个空隙中选出k-1个空隙放挡板，形成的k个数的和正好就是n。
换句话说，我们要求C_{n-1}^{k-1}
对于样例的画图辅助理解

代码

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int MAXN = 100, mod = 1000, inf = 1000000;
ll k, x, n;
ll sum[MAXN], cnt = 1;

ll qpow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1)ans = ans * a%mod;
        a = a * a%mod;
        b >>= 1;
    }
    return ans;
}

void c(ll n, ll m) {
    sum[1] = 1, cnt = 1;
    for (int i = m; i >= m - n + 1; i--) {//对组合数公式进行了化简
        for (int j = 1; j<MAXN; j++) {
            sum[j] *= i;
        }
        for (int j = 1; j<MAXN; j++) {
            if (sum[j] >= inf) {
                sum[j + 1] += sum[j] / inf;
                sum[j] %= inf;
            }
        }
    }
    for (int i = 2; i <= n; i++) {
        for (int j = MAXN-1; j >= 1; j--) {
            if (sum[j] == 0)   continue;
            if (sum[j] >= i) {
                sum[j - 1] += sum[j] % i*inf;
                sum[j] /= i;
            }
            else sum[j - 1] += sum[j] * inf, sum[j] = 0;
        }
    }
}

int main() {
    ll k, x;
    cin >> k >> x;
    n = qpow(x, x);
    if (k - 1 <= 0 || n - 1 <= 0) {
        printf("0");
        return 0;
    }
    c(k - 1, n - 1);//总共有n-1个间隙，要插k-1个隔板；
    int id;
    for (int i = MAXN - 1; i >= 1; i--) {
        if (sum[i]) {
            id = i;
            break;
        }
    }
    printf("%lld", sum[id]);
    for (int i = id-1; i >= 1; i--) {
        printf("%06lld", sum[i]);
    }
    return 0;
}