题目描述
佳佳碰到了一个难题，请你来帮忙解决。
对于不定方程a1+a2+…+ak-1+ak=g(x)，其中k≥2且k∈N，x是正整数，g(x)=x^x mod 1000(即x^x除以1000的余数)，x，k是给定的数。我们要求的是这个不定方程的正整数解组数。
举例来说，当k=3，x=2时，分别为(a1,a2,a3)=(2,1,1)’(1,2,1)，(1,1,2)。 输入输出格式 输入格式：
输入文件equation.in有且只有一行，为用空格隔开的两个正整数，依次为k，x。
输出格式：
输出文件equation.out有且只有一行，为方程的正整数解组数。
快速幂求出g(x)。 考虑裸的dp方程，dp[i][j]表示i个数和为j的方案数，dp[i][j]=Σdp[i-1][i-1…j-1]，时间复杂度为O(k*mod^2)。 注意到边界条件dp[0][0]=1，其他所有值都由它推得，从刷表的角度考虑，dp[i][j]每次一定走到dp[i+1][j+x]，最终要走到dp[k][g]。不妨看成要走k步，每一步可以走一个或一个以上的格子，最后总共要走g个格子，问方法总数。 这样就变成了计数问题，即要在(g-1)个间隔中选出(k-1)个，答案是c(g-1,k-1)。 注意使用高精度。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define LL long long const int bit=10000; const int mod=1000; struct NUM { int a[100],l; NUM operator + (const NUM & x) { NUM ret; ret.a[1]=0; for (int i=1;i<=l||i<=x.l;i++) { ret.a[i]+=a[i]+x.a[i]; ret.a[i+1]=ret.a[i]/bit; ret.a[i]%=bit; } ret.l=max(l,x.l); if (ret.a[ret.l+1]) ret.l++; return ret; } void out() { int i,j,k,x,y,z; printf("%d",a[l]); for (i=l-1;i;i--) { if (a[i]<10) printf("000"); else { if (a[i]<100) printf("00"); else { if (a[i]<1000) printf("0"); } } printf("%d",a[i]); } printf("\n"); } }c[1010][110]; int pw(int x) { int base=x%mod,ans=1; for (;x;x>>=1,base=(base*base)%mod) if (x&1) ans=(ans*base)%mod; return ans; } int main() { int i,j,k,m,n,p,q,x,y,z; scanf("%d%d",&k,&x); m=pw(x); for (i=0;i<m;i++) c[i][0].a[1]=c[i][0].l=1; for (i=1;i<m;i++) for (j=1;j<k;j++) c[i][j]=c[i-1][j-1]+c[i-1][j]; c[m-1][k-1].out(); }