自动搬运

查看原文

来自洛谷，原作者为

	KesdiaelKen **

搬运于2025-08-24 21:27:14，当前版本为作者最后更新于2018-06-30 14:58:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

题目要求的是：

$$\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;
}