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;

}

巴特西

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

最新文章

热门文章