自动搬运

查看原文

来自洛谷，原作者为

	小粉兔 Always continue; Never break;

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

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

以下是正文

数位DP(二进制)计算出G[i]为恰好有i个的方案数。

答案为$\prod i^{G[i]}$，快速幂解决。

#include<cstdio>
#define LL long long
#define M 10000007
LL N,Ans=1;
LL C,G[50];
LL qPow(LL b,LL e){LL A=1;for(;e;b=b*b%M,e>>=1)e&1?A=A*b%M:0;return A;}
int main(){
	scanf("%lld",&N);
	for(int j=49;~j;--j){
		for(int i=49;i;--i)
			G[i]+=G[i-1];
		if(N>>j&1) ++G[C++];
	} ++G[C];
	for(int i=1;i<=49;++i)
		Ans=Ans*qPow(i,G[i])%M;
	printf("%lld",Ans);
	return 0;
}