牛牛P50591 解的分配问题，高精度组合数

题意：

给出不定方程
$$a_1+a_2+...+a_k=x^x(mod1000)$$
求出有多少组正整数解

Solution：

解的分配问题考虑隔板法，两个隔板之间的小球数是一个解，每个隔板之前的到前一个隔板的小球数就是一个解，第一个小球前不用放置一个隔板，但最后一个小球后面一定需要放置一个隔板，那么只需要在剩下的$x^x(mod1000)-1$个位置中放置$k-1$个隔板，即
$$C_{x^x(mod1000)-1}^{k-1}$$
这个需要高精度加法或乘法，切莫使用NTT做，自带取余，可以考虑FFT求高精度积，总而言之，高精度加是最优的

也可以考虑生成函数，每个解的生成函数为
$$f(x^{\prime })=\sum _{i=1}^{x^x(mod1000)}{x}^{\prime i}$$
对这个多项式求$k$次幂即可，但数字太大，不如高精度，并且需要NTT，自带取余，会使得答案不准确

// #include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

using ll=long long;
const int N=2e7,inf=0x3fffffff;
const long long INF=0x3f3f3f3f3f3f,mod=1e3;

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

vector<int>operator+(vector<int>val1,vector<int>val2)
{
    if(val1.size()<val2.size()) swap(val1,val2);
    reverse(val1.begin(),val1.end()); reverse(val2.begin(),val2.end());
    vector<int>ret(val1.size());
    for(int i=0;i<val2.size();i++) ret[i]=val1[i]+val2[i];
    for(int i=val2.size();i<val1.size();i++) ret[i]=val1[i];
    for(int i=0;i<ret.size();i++)
    {
        if(ret[i]>9)
        {
            if(i+1<ret.size()) ret[i+1]+=ret[i]/10;
            else ret.push_back(ret[i]/10);
            ret[i]%=10;
        }
    }
    reverse(ret.begin(),ret.end());
    return ret;
}

ll k,x;
vector<int>C[1005][105];

int main()
{
    #ifdef stdjudge
        freopen("in.txt","r",stdin);
    #endif 
    cin>>k>>x;
    ll tmp=qpow(x,x);
    C[0][0]={1};
    for(int i=1;i<=tmp;i++)
    {
        for(int j=0;j<=105;j++)
        {
            if(j==0||j==i) C[i][j]={1};
            else C[i][j]=C[i-1][j-1]+C[i-1][j];
        }
    }
    if(k>tmp) cout<<0;
    else
    {
        for(int i=0;i<C[tmp-1][k-1].size();i++) printf("%d",C[tmp-1][k-1][i]);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74