Cogs 604.方程（排列组合+高精度）

方程
★☆ 输入文件：equationz.in 输出文件：equationz.out 简单对比
时间限制：1 s 内存限制：128 MB
【题目描述】
hyc 碰到了一个难题，请你来帮忙解决。
对于不定方程a1+a2+a3+……+ak=g(x) ，其中K.>=2,k是正整数 , x 是正整数
g(x)=x^x mod 1000 , x,k 是给定的数 . 我们要求的是这个不定方程的正整数解组数 .
举例来说 , 当 k=3,x=2 时 ,g(x)=4, 原方程即 A1+A2+A3=4 .
这个方程的正整数解有 3 组 . 分别为 (A1,A2,A3) = （2，1，1），（1，2，1），（1，1，2）.
【输入文件】
有且只有一行 . 为用空格隔开的两个正整数 , 依次为 k,x.
【输出文件】
有且只有一行 , 为方程的正整数解组数 .
【样例输入】
3 2
【样例输出】
3
【数据范围】
对于 40% 的数据 , ans<= 10^16 ;
对于 100% 的数据 , k<=100 , x<= 2^31-1 ,k<=g(x)。

/*
求不定方程正整数解的个数.
隔板法求得ans=C(m-1,n-1) (m=pow(x,x)%1000).
然后是恶心的高精度..... 
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
#define mod 1000
#define MAXN 1001
using namespace std;
int n,x,m,f[MAXN][MAXN*10],tmp1[MAXN],a[MAXN*10],tmp[MAXN*10],tmpc[MAXN*10],tot;
int read()
{
    LL x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
    return x*f;
}
LL mi(LL a,LL b)
{
    LL total=1;
    while(b)
    {
        if(b&1) total=total*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return total;
}
void slove1(int x)
{
    tot=0;
    while(x) tmp[++tot]=x%10,x/=10;tmp[0]=tot;return ;
}
void add(int c[],int a[],int b[])
{
    c[0]=a[0]+b[0];
    for(int i=1;i<=a[0];i++)
    {
        int x=0;
        for(int j=1;j<=b[0];j++)
        {
            c[i+j-1]+=a[i]*b[j];
            c[i+j]+=c[i+j-1]/10;
            x=c[i+j-1]/10;
            c[i+j-1]%=10;
        }
        c[i+b[0]]=x;
    }
    if(c[c[0]+1]) c[0]++;
    while(!c[c[0]]&&c[0]>1) c[0]--;return ;
}
bool cmp(int a[],int b[])
{
    if(a[0]>b[0]) return true;
    if(a[0]<b[0]) return false;
    for(int i=a[0];i>=1;i--)
    {
        if(a[i]>b[i]) return true;
        if(a[i]<b[i]) return false;
    }
    return true;
}
void jian(int a[],int b[])
{
    for(int i=1;i<=b[0];i++)
    {
        if(a[i]<b[i]) a[i]+=10,a[i+1]--;
        a[i]-=b[i];
    }
    while(!a[a[0]]&&a[0]>1) a[0]--;
    return ;
}
void chu(int c[],int a[],int b[])
{
    c[0]=a[0]-b[0]+1;
    for(int i=c[0];i>=1;i--)
    {
        memset(tmpc,0,sizeof tmpc);
        for(int j=1;j<=b[0];j++) tmpc[i+j-1]=b[j];
        tmpc[0]=b[0]+i-1;
        while(cmp(a,tmpc))
          c[i]++,jian(a,tmpc);
    }
    while(!c[c[0]]&&c[0]>1) c[0]--;
    return;
}
void slove()
{
    f[0][0]=1;f[0][1]=1;
    for(int i=1;i<=n;i++)
    {
        slove1(m-i+1);
        add(f[i],tmp,f[i-1]);
        slove1(i);
        memset(tmp1,0,sizeof tmp1);
        chu(tmp1,f[i],tmp);
        for(int j=0;j<=tmp1[0];j++) f[i][j]=tmp1[j];
    }
    for(int i=f[n][0];i>=1;i--) printf("%d",f[n][i]);
}
int main()
{
    freopen("equationz.in","r",stdin);
    freopen("equationz.out","w",stdout);
    n=read(),x=read();
    m=mi(x,x);m--,n--;
    slove();
    return 0;
}