1653：方程的解

【题目描述】
佳佳碰到了一个难题，请你来帮忙解决。对于不定方程 a1+a2+⋯+ak−1+ak=g(x)，其中 k≥2 且 k∈N∗ ，x 是正整数，g(x)=xxmod1000（即 xx 除以 1000 的余数），x,k 是给定的数。我们要求的是这个不定方程的正整数解组数。

举例来说，当 k=3,x=2 时，方程的解分别为：

⎧⎩⎨a1=1a2=1a3=2⎧⎩⎨a1=1a2=2a3=1⎧⎩⎨a1=2a2=1a3=1
【输入】
有且只有一行，为用空格隔开的两个正整数，依次为 k,x。

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

【输入样例】
3 2
【输出样例】
3
【提示】
数据范围与提示：

对于 40% 数据，答案不超过 1016 ；

对于全部数据，1≤k≤100,1≤x<231,k≤g(x)。

#include <iostream>
using namespace std;
const int N=200;
int n,k;
int x;
const int Mod =1000;
int f[1000][100][N];
int quick_pow(int a,int b) {
	int ret=1;
	while(b) {
		if(b & 1) ret= ret * a % Mod;
		a= a * a % Mod;
		b>>=1;
	}
	return ret;
}
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=quick_pow(x%Mod,x);
	for(int i = 0; i <= n ; i++){
		for(int j=0;j <= i && j < k; j++){
			if(!j) f[i][j][0]=1;
			else add(f[i][j],f[i-1][j-1],f[i-1][j]);
		}
	}
	int *g = f[n-1][k-1];
	int k=N-1;
	while(!g[k]) k--;
	while(k>=0) cout<<g[k--];
	return 0;
}