方程的解

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2455 字
对不定方程a_1+a_2+...+a_k=g
一本通
练习
正文

/*
原题：T1653「一本通 6.6 练习 2」方程的解
题意：对不定方程 a_1+a_2+...+a_k=g(x)，其中 g(x)=x^x mod 1000，求正整数解的组数。
思路：正整数解即把 g(x) 个 1 分成 k 份，用隔板法得 C(g(x)-1, k-1)。
g(x) 用快速幂在模 1000 下算出；组合数可能极大，用高精度整数，
按递推 res=res·(n-r+i)/i 逐步乘除计算，每步都能整除。
复杂度：时间 O(log x + k·精度位数)，空间 O(精度位数)
易错点：1) g(x) 可能为 0，或小于 k，此时无正整数解，输出 0；
2) 隔板法是 C(g-1,k-1) 而不是 C(g,k)；
3) 高精度要用 setw(4) 补前导零输出中间段。
*/
#include <bits/stdc++.h>
using namespace std;
const int BASE=10000;
struct Big{
    vector<int> d;
    Big(long long v=0){
        if(v==0){
            d.push_back(0);
        }else{
            while(v>0){
                d.push_back(v%BASE);
                v/=BASE;
            }
        }
    }
    void trim(){
        while(d.size()>1 && d.back()==0){
            d.pop_back();
        }
    }
};
Big mulSmall(const Big& x,long long m){
    Big r;
    size_t n=x.d.size()+40;
    vector<long long> tmp(n,0);
    for(size_t i=0;i<x.d.size();i++){
        long long cur=(long long)x.d[i]*m;
        size_t j=i;
        while(cur>0 && j<n){
            tmp[j]+=cur%BASE;
            cur/=BASE;
            j++;
        }
    }
    r.d.assign(n+2,0);
    long long carry=0;
    for(size_t i=0;i<n+2;i++){
        long long cur=(i<n?tmp[i]:0)+carry;
        r.d[i]=cur%BASE;
        carry=cur/BASE;
    }
    while(carry>0){
        r.d.push_back(carry%BASE);
        carry/=BASE;
    }
    r.trim();
    return r;
}
Big divSmall(const Big& x,int m){
    Big r;
    r.d.assign(x.d.size(),0);
    long long rem=0;
    for(size_t i=x.d.size();i-- >0;){
        long long cur=rem*BASE+x.d[i];
        r.d[i]=cur/m;
        rem=cur%m;
    }
    r.trim();
    return r;
}
Big comb(long long n,int r){
    if(r<0 || n<r){
        return Big(0);
    }
    if(r==0){
        return Big(1);
    }
    Big res(1);
    for(int i=1;i<=r;i++){
        res=mulSmall(res,n-r+i);
        res=divSmall(res,i);
    }
    return res;
}
long long qpow(long long a,long long n,long long mod){
    long long r=1%mod;
    a%=mod;
    while(n>0){
        if(n&1){
            r=r*a%mod;
        }
        a=a*a%mod;
        n>>=1;
    }
    return r;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long k,x;
    cin>>k>>x;
    long long g=qpow(x,x,1000);
    if(g<k){
        cout<<0<<"\n";
        return 0;
    }
    Big ans=comb(g-1,(int)(k-1));
    cout<<ans.d.back();
    for(int i=(int)ans.d.size()-2;i>=0;i--){
        cout<<setw(4)<<setfill('0')<<ans.d[i];
    }
    cout<<"\n";
    return 0;
}
方程的解

正文

一本通·提高篇的其它内容
