[竟然学过的东西都忘了]方程的解

时间：2010-09-22 来源：Sephiroth Lee

【描述】

一个方程组x1+x2+...+xn=p。

其中 x1>=a1,x2>=a2,...,xn>=an。

现给出a数列，求方程的所有非负整数解共多少种。

【输入描述】

有n+2行数据。第一行为n，接下来的n行为a数列。最后一行为p。

【输出描述】

非负整数解的个数。

【样例输入】

【样例输出】

【分析】

因为每个x有一个下限，我们设n1=p-tot,tot=a数列的和。那么题目就是b1+b2+...+bn=n1，其中bi>=0的非负整数解的总数。这是高中数学排列组合中的问题。

假设有n1个球，我们在其中插入n-1个隔板，允许挡板之间没有球。这样的方案总数就是我们要求的。

可以将其看为一共n1+n-1个球，我们选出n-1个球。就是C(n1+n-1),(n-1)=(n1+n-1)!/((n-1)!*(n1)!)。

因为n1和n-1都很小，所以高精度也很好写。

#include <stdio.h>
#include <string.h>
#define maxn 210

int len,p,n,tem,tot,n1,n2;
int ans[maxn],k,now,te[maxn];

int main()
{
    freopen("equation.in","r",stdin);
    freopen("equation.out","w",stdout);
    
    scanf("%d",&n);
    for (int i=1;i<=n;++i)
    {
        scanf("%d",&tem);
        tot+=tem;
    }
    scanf("%d",&p);
    n1=p-tot;
    n2=n-1;
    ans[1]=1;
    len=1;
    for (int i=n1+n2;i>1;--i)
    {
        k=0;
        for (int j=1;j<=len+1;++j)
        {
            ans[j]=ans[j]*i+k;
            k=ans[j]/10000;
            ans[j]%=10000;
        }
        while (ans[len+1]) ++len;
    }
    for (int i=n1;i>1;--i)
    {
        memset(te,0,sizeof(te));
        for (k=1;k<=len;++k) te[k]=ans[k];
        for (k=len;k>0;--k)
        {
            ans[k]=te[k]/i;
            te[k-1]+=(te[k]%i)*10000;
        }
        while (!ans[len]) --len;
    }
    for (int i=n2;i>1;--i)
    {
        memset(te,0,sizeof(te));
        for (k=1;k<=len;++k) te[k]=ans[k];
        for (k=len;k>0;--k)
        {
            ans[k]=te[k]/i;
            te[k-1]+=(te[k]%i)*10000;
        }
        while (!ans[len]) --len;
    }
    printf("%d",ans[len]);
    for (int i=len-1;i>0;--i) printf("%d%d%d%d",ans[i]/1000,ans[i]/100%10,ans[i]/10%10,ans[i]%10);
    return 0;
}