社区讨论

论一种猎奇的O(n)求n!的方式

GGcend
学术版参与者 21已保存回复 36

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
36 条
当前快照
1 份
快照标识符
@mhjcw01g
此快照首次捕获于
2025/11/04 00:30
4 个月前
此快照最后确认于
2025/11/04 06:10
4 个月前
查看原帖
我们发现目前较为正常的求 n!n! 的做法都是通过 (n−1)!(n-1)! 递推或递归求出答案。
考虑如何变成小唐人，如果你有一双智障的眼睛可以发现， n!=(n⌊n2⌋)×⌊n2⌋!×⌈n2⌉!n!=\binom{n}{\lfloor \frac{n}{2} \rfloor} \times \lfloor \frac{n}{2} \rfloor! \times \lceil \frac{n}{2} \rceil!
我们分奇偶讨论，
当 nn 为偶数时，上式与下面的式子等价。 n!=(nn2)×(n2)!×(n2)!n!=\binom{n}{\frac{n}{2}} \times (\frac{n}{2})! \times (\frac{n}{2})! 当 nn 为奇数时，上式与下面的式子等价。 n!=(nn+12)×(n−12)!×(n−12)!×n+12n!=\binom{n}{\frac{n+1}{2}} \times (\frac{n-1}{2})! \times (\frac{n-1}{2})!\times \frac{n+1}{2} 注意到这和快速幂的形式是相似的。
考虑递归发现可以做到 O(log⁡n)O(\log n) 求 n!n!。
但我们该如何求 (n⌊n2⌋)\binom{n}{\lfloor \frac{n}{2} \rfloor} ，我们可以采取递推的方法。
我们知道 (nk)=(n−1k−1)×nk\binom{n}{k}=\binom{n-1}{k-1} \times \frac{n}{k}， 那么将 k←⌈n2⌉k \gets \lceil \frac{n}{2} \rceil 我们就证明了这是可以 O(n)O(n) 预处理的。
可是就算如此，对于每个 nn 以快速幂的形式求 n!n! ，需要 O(nlog⁡n)O(n \log n)，但是显然，我们可以记忆化，最终时间复杂度 O(n)O(n)。

code

C
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,p=998244353;
int inv[N],ans[N],C[N];
void quick_pow(int x){
	if(ans[x]!=0) return ;
	if(x==1) return ;
	quick_pow(x/2);
	if(x&1) ans[x]=C[x]*ans[x/2]%p*ans[x/2]%p*(x+1)%p*inv[2]%p;
	else ans[x]=C[x]*ans[x/2]%p*ans[x/2]%p;
	return ;
}
signed main(){
	int n;
	cin >>n;
	inv[1]=C[0]=C[1]=ans[1]=1;
	for(int i=2;i<=n;i++){
		inv[i]=p-(p/i)*inv[p%i]%p;
		C[i]=C[i-1]*i%p*inv[(i+1)/2]%p;
	}
	for(int i=n;i>0;i--) quick_pow(i);
	for(int i=1;i<=n;i++) cout <<ans[i]<<" ";
//	cout <<ans[n];
	return 0;
}
只输出 ans[n] 可以通过P5739。

回复

共 36 条回复，欢迎继续交流。

正在加载回复...