Description

【题意】
对于不定方程 $a_1+a_2+\cdots +a_{k-1}+a_k=g(x) $，其中 $k\ge 2$ 且 $k\in \mathbb{N}^* $，$x$ 是正整数，$g(x)=x^x \bmod 1000 $（即 $x^x $ 除以 $1000$ 的余数），$x，k$ 是给定的数。我们要求的是这个不定方程的正整数解组数。
举例来说，当 $k=3，x=2$ 时，方程的解分别为：
$\begin{cases} a_1=1\\ a_2=1\\ a_3=2 \end{cases}$        $\begin{cases} a_1=1\\ a_2=2\\ a_3=1 \end{cases}$        $\begin{cases} a_1=2\\ a_2=1\\ a_3=1 \end{cases}$

【输入格式】
输入有且只有一行，为用空格隔开的两个正整数，依次为 $k，x$。

【输出格式】
输出有且只有一行，为方程的正整数解组数。

【样例输入】
3 2

【样例输出】
3

【提示】
- 对于 $40\%$ 的数据，$ans \le 10^{16} $；
- 对于 $100\%$ 的数据，$k \le 100 $，$x \le 2^{31}-1 $，$k \le g(x) $。

Hint

#include<bits/stdc++.h> 
using namespace std; 
typedef long long LL; 
const int mod=1e9;
struct node
{
    LL a[110];int len;
    node(){memset(a,0,sizeof(a));len=1;}
};
node operator* (node n1,int x)
{
node no;no.len=n1.len;
for(int i=1;i<=no.len;i++)no.a[i]=n1.a[i]x;
for(int i=1;i<=no.len;i++)no.a[i+1]+=no.a[i]/mod,no.a[i]%=mod;
int i=no.len;
while(no.a[i+1]>0)
{
i++,no.a[i+1]+=no.a[i]/mod,no.a[i]%=mod;
}
no.len=i;
return no;
}
int ksm(int a,int b)

{
int res=1;a=a%1000;
for(;b;b>>=1,a=aa%1000)if(b&1)res=res*a%1000;
return res;
}
int a[110],b[110];
node C(int n,int m)

{
node no;
if(m>n)return no;
for(int i=1;i<=m;i++)a[i]=n-i+1,b[i]=i;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)
{
if(b[i]==1) break;
int d= __gcd(b[i],a[j]);
b[i]/=d;
a[j]/=d;
}
}
no.a[1]=1;
for(int i=1;i<=m;i++)no=no*a[i];
return no;

}
int main()

{
int k,x;cin>>k>>x;
x=ksm(x,x);
node ans=C(x-1,k-1);//插板法
printf("%lld",ans.a[ans.len]);
for(int i=ans.len-1;i>=1;i--)printf("%09lld",ans.a[i]);
printf("\n");
return 0;

}  

</p>