$x^{x}{~}mod{~}1000$可以用快速幂求
求$a_{1}+…+a_{k} = n$正整数解数量
隔板法:
例
$a_{1}+a_{2}+a_{3} = 4$
o | o o | o
$a_{1}=1 \\\\ a_{2}=2 \\\\ a_{3}=1$
3个未知数<=>
3个部分<=>
2个隔板
总数4<=>
4个小球
则问题转化为$g(x)个小球,g(x)-1个空隙,k-1个板子$
答案
$C_{g(x)-1}^{k-1}$
通过递推式$C_{n}^{m} = C_{n-1}^{m}+C_{n-1}^{m-1}$初始化$C$
高精度
$C_{1000}^{100} ≈ \frac{1000^{100}}{100!} ≈ \frac{300位}{157位} = 143位$
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 150;
int k, x;
int f[1000][100][N];
int qmi(int a,int k,int p)
{
int res = 0;
while(k)
{
if(k&1)res=res*a%p;
a = a*a%p;
k>>=1;
}
return res;
}
void add(int c[],int a[],int b[])
{
for(int i=0,t=0;i<N;i++)
{
t+=a[i]+b[i];
c[i]=t%10;
t/=10;
}
}
int main()
{
cin >> k >> x;
int n=qmi(x%1000,x,1000);
for(int i=0;i<n;i++)
for(int j=0;j<=i && j<k;j++)
if(!j) f[i][j][0]=1;//j=0时 f[i][j]=1
else add(f[i][j],f[i-1][j],f[i-1][j-1]);
int *g = f[n-1][k-1];
int i = N-1;
while(!g[i])i--;//找最高一位不是0的位
//123 cout << 1 << 2 << 3;先从高位输出
while(i>=0)cout<<g[i--];
return 0;
}
代码错了,快速幂里res初始化为1