自动搬运

查看原文

来自洛谷，原作者为

	RainFestival 时代的眼泪|我们所过的每个平凡的日常，也许就是连续发生的奇迹

搬运于2025-08-24 21:25:41，当前版本为作者最后更新于2019-02-03 16:15:52，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

update on $\sf 2021.12.22$

以下定义 $x\in P$ 为 $x$ 是质数。

这个题目让我们求 $\binom{n+m}{m}\bmod 10^{100}$。

显然需要高精度计算。如果你使用朴素的高精，$(n+m)!$ 可能会达到 $10^5!$，大概有 $400000$ 多位。

这个 $400000$ 多位是对它取对数得到的，$\log_{10}(10^5!)\approx 456573.45$。

朴素高精乘法很慢，对于两个位数为 $n$ 的数相乘，相当于暴力卷积，是 $\mathcal{O(n^2)}$ 的，不能在本题限制内解决问题。

更重要的是，还要涉及到高精度除法。

所以我们要换一种做法。

我们把 $[1,n+m]$ 中的每一个质数数找出来，然后考虑每一个质数出现了多少次。

我们知道 $\binom{n+m}{m}=\frac{(n+m)!}{n!m!}$。

假设 $p\in P$，$f_p=(n+m)!$ 的唯一分解中 $p$ 的次数，$a_p=n!$ 的唯一分解中 $p$ 的次数，$b_p=m!$ 的唯一分解中 $p$ 的次数。

那么答案为 $\prod\limits_{p\in P}p^{f_p-a_p-b_p}$。

记录 $s_p=f_p-a_p-b_p$，考虑求出 $s$。

对于分子部分，每一个质因数的贡献是 $+1$，对于分母，则是 $-1$。

我们知道 $n$ 以内的质数数量 $\pi(n)\approx \frac{n}{\ln n}$ 而 $n=100000$ 时，$\pi(100000)=9592$。

记得一边做高精乘法一边取模，就是说，高精的位数不能超过 $100$ 位。

代码：

#include<cstdio>
#include<algorithm>
int n,m,l,maxn,t[100005],p[100005],cnt[100005];
long long ss[105];
void mul(int x) 
{
	for (int i=1;i<=l;i++) ss[i]=ss[i]*x;
	for (int i=1;i<=l||ss[i];i++) ss[i+1]=ss[i+1]+ss[i]/10,ss[i]=ss[i]%10,l=std::max(l,i);
	l=std::min(l,100);
}
void add(int x,int w)
{
	while (x>1)
	{
		int d=t[x];
		cnt[d]=cnt[d]+w;
		x=x/d;
	}
}
int main()
{
	ss[l=1]=1;
	scanf("%d%d",&n,&m);
	maxn=n+m;
	for (int i=2;i<=maxn;i++) p[i]=1;
	for (int i=2;i<=maxn;i++)
	{
		if (!p[i]) continue;
		t[i]=i;
		for (int j=i,l=maxn/i;j<=l;j++) p[i*j]=0,t[i*j]=i;
	}
	for (int i=1;i<=n+m;i++) add(i,1);
	for (int i=1;i<=n;i++) add(i,-1);
	for (int i=1;i<=m;i++) add(i,-1);
	for (int k=1;k<=n+m;k++) for (int i=1;i<=cnt[k];i++) mul(k);
	for (int i=100;i>=1;i--)
	{
		printf("%lld",ss[i]);
		if (i%10==1) puts("");
	}
	return 0;
}

实测时间 $\tt 77ms$，空间 $\tt 1.39MB$，代码长度 $\tt 873B$。

当然如果不限制高精位数也是可以通过的，$n=50000,m=50000$ 也能在 $\tt 1s$ 内跑完。

个人吐槽：本题解是我近 $3$ 年前写的，看到它成为本题最高赞的题解，我就修改一下排版与格式的问题。原来的存档在这里。感谢各位的阅读与支持。当时我很菜，啥题都不会做，做这个题目花了不少时间，但是我当时记得在哪里看到过这个做法，然后就做出来了，当时也挺高兴的。但是现在想想就不知有当时多么菜与浅薄了。