洛谷P4317 花神的数论题 题解

description：

solution:

$g\left[i\right]表示二进制下有i个1时的方案数$g[i]表示二进制下有i个1时的方案数

则答案为

$\prod i^{G\left[i\right]}$∏iG[i]

然后别忘了用快速幂，因为 $g\left[i\right]$g[i]会很大

code:

#include<cstdio>
using namespace std;
long long quick(long long x,long long y)
{
	long long r=1;
	while(y)
	{
		if(y&1)
		{
			r=r*x%10000007;
		}
		x=x*x%10000007;
		y=y/2;
	}
	return r;
}
long long g[105];
int main()
{
	long long n;
	long long cnt=0;
	scanf("%lld",&n);
	for(long long i=49;~i;i--)
	{
		for(long long j=49;j;j--)
		{
			g[j]+=g[j-1];
		}
		if(n>>i&1)
		{
			++g[cnt++];
		}
	}
	++g[cnt];
	long long ans=1;
	for(long long i=1;i<=49;i++)
	{
		ans=(ans*quick(i,g[i]))%10000007;
	}
	printf("%lld\n",ans);
	return 0;
}