题解 P1625 【求和】

· · 题解

想要成为信息学大佬，就一定要学好小学奥数……

题目要求的是：

\prod_{i=1}^{n}(\frac{1}{\prod_{j=i}^{m+i-1}j})

我们想办法对其进行裂项求和

我们先来看这个多项式乘积中的其中任意一项。它可以表示为：

\frac{1}{k(k+1)(k+2)...(k+m-1)}

我们需要想办法对其进行裂项。来看这个式子：

\frac{1}{k(k+1)(k+2)...(k+m-2)}-\frac{1}{(k+1)(k+2)(k+3)...(k+m-1)}

我们将两个分数通分：

\frac{(k+m-1)-k}{k(k+1)(k+2)...(k+m-1)}

即

\frac{m-1}{k(k+1)(k+2)...(k+m-1)}=\frac{1}{k(k+1)(k+2)...(k+m-1)}*(m-1)

所以

\frac{1}{k(k+1)(k+2)...(k+m-1)} =\frac{1}{m-1}*\frac{m-1}{k(k+1)(k+2)...(k+m-1)} =\frac{1}{m-1}*(\frac{1}{k(k+1)(k+2)...(k+m-2)}-\frac{1}{(k+1)(k+2)(k+3)...(k+m-1)})

所以我们对原式进行变换

\prod_{i=1}^{n}(\frac{1}{\prod_{j=i}^{m+i-1}j}) =(\frac{1}{m-1})(\frac{1}{1*...*(m-1)}-\frac{1}{2*...*m}+\frac{1}{2*...*m}-\frac{1}{3*...*(m+1)} +...+\frac{1}{n*...*(n+m-2)}-\frac{1}{(n+1)*...*(n+m-1)})

中间项全都互相抵消

=(\frac{1}{m-1})(\frac{1}{1*...*(m-1)}-\frac{1}{(n+1)*...*(n+m-1)})

通分

=\frac{(\prod_{i=n+1}^{n+m-1})-(\prod_{i=1}^{m-1})}{(m-1)(\prod_{i=1}^{m-1})(\prod_{i=n+1}^{n+m-1})}

显然无法继续化简了。于是，我们需要用到高精度。

先把分母分子算出来，然后进行化简，即检查分母分子是否有相同因数，有则除去。注意：因为分母是由若干小于等于n+m-1的数相乘得到，所以分母的最大质因数不会超过n+m-1，即化简时除数的最大边界设为n+m-1即可。

高精减、乘、除都需要用到……祝您打代码愉快。

代码如下：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<iostream>
using namespace std;
int n,m;
struct GJD//高精度结构体
{
    char shu[50000];
    int len;
    GJD(){memset(shu,0,sizeof(shu));len=0;}
}mm,nn,_1,lc,nn1,nn2;//mm为分母，nn为分子
int x;
GJD times(GJD a,int b)//乘法
{
    x=0;
    memset(lc.shu,0,sizeof(lc.shu));lc.len=0;
    while(lc.len<=a.len||x)
    {
        x+=a.shu[lc.len]*b;
        lc.shu[lc.len]=x%10;
        x/=10;
        lc.len++;
    }
    while(lc.shu[lc.len-1]==0)
    {
        lc.shu[lc.len-1]=0;
        lc.len--;
    }
    return lc;
}
GJD minu(GJD a,GJD b)//减法
{
    memset(lc.shu,0,sizeof(lc.shu));lc.len=0;
    x=0;
    while(lc.len<=a.len||x!=0)
    {
        x+=a.shu[lc.len]-b.shu[lc.len];
        if(x>=0)
        {
            lc.shu[lc.len]=x;
            x=0;
        }
        else
        {
            lc.shu[lc.len]=x+10;
            x=-1;
        }
        lc.len++;
    }
    while(lc.shu[lc.len-1]==0)
    {
        lc.shu[lc.len-1]=0;
        lc.len--;
    }
    return lc;
}
bool equals(GJD a,GJD b)//判断是否相等（用于判断是否整除）
{
    if(a.len!=b.len)return false;
    for(int i=0;i<a.len;i++)
    {
        if(a.shu[i]!=b.shu[i])return false;
    }
    return true;
}
GJD divide(GJD a,int b)//除法
{
    x=0;
    memset(lc.shu,0,sizeof(lc.shu));lc.len=0;
    for(int i=a.len-1;i>=0;i--)
    {
        x=x*10+a.shu[i];
        lc.shu[lc.len]=x/b;lc.len++;
        x=x%b;
    }
    for(int i=0;i<=(lc.len-1)/2;i++)swap(lc.shu[i],lc.shu[lc.len-1-i]);
    while(lc.shu[lc.len-1]==0)
    {
        lc.shu[lc.len-1]=0;
        lc.len--;
    }
    return lc;
}
void print(GJD a)//输出
{
    for(int i=a.len-1;i>=0;i--)printf("%d",(int)a.shu[i]);
    printf("\n");
}
int main()
{
    scanf("%d%d",&n,&m);
    _1.shu[0]=1;_1.len=1;nn1=nn2=_1;
    mm=times(_1,m-1);
    for(int i=1;i<=m-1;i++)mm=times(mm,i);
    for(int i=n+1;i<=n+m-1;i++)mm=times(mm,i);
    for(int i=n+1;i<=n+m-1;i++)nn1=times(nn1,i);
    for(int i=1;i<=m-1;i++)nn2=times(nn2,i);
    nn=minu(nn1,nn2);
    for(int i=2;i<=n+m-1;i++)
    {
        while(equals(times(divide(nn,i),i),nn)&&equals(times(divide(mm,i),i),mm))//如果a/b*b=a，则b|a
        {
            nn=divide(nn,i);
            mm=divide(mm,i);
        }
    }
    print(nn);print(mm);
    return 0;
}