Description:

设 $sum_i$ 表示 $i$ 的二进制表示中 $1$ 的个数。给出一个正整数 $N$ ，求 $\prod_{i=1}^{N} Sum_i$

$1 \le N \le 10^{15}$

Solution:

数位 $DP$ ，设 $c[i][j]$ 表示 $i$ 为中有 $j$ 个 $1$ 的数的个数， $c[i][j]=c[i-1][j-1]+c[i-1][j]$ ，分别代表最后一位放不放 $1$ ，在 $DP$ 时枚举每一位，再枚举对于这一位所包含的区间（ $···100···00$ ~ $···111···11$ ）有多少个一，则落在这个区间内的 $1$ 就有 $j-cnt$ 个， $cnt$ 是他之上的 $1$ 的位数，所以需要从高位向低位枚举，注意由于是乘，所以 $c[][]$ 是指数，根据欧拉定理应该模 $\varphi(P)$ ，注意由于统计的区间是 $(1 << (i - 1))$ ~ $(1 << i) - 1$ ，所以在刚开始要加 $1$ 。

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MOD 10000007

#define PHI 9988440  

typedef long long ll;

ll n;

ll c[64][64];

ll f[64];

ll power(ll a,ll b)

{

	ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = (res * a) % MOD;

		a = (a * a) % MOD;

		b = b >> 1;

	}

	return res;

}

int main()

{

	cin >> n;

	++n;

	for(int i = 0;i <= 63;++i)c[i][0] = c[i][i] = 1;

	for(int i = 1;i <= 63;++i)for(int j = 1;j <= i;++j)c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % PHI;

	memset(f,0,sizeof(f));

	ll ans = 1;int cnt = 0;

	for(int i = 63;i >= 0;--i)

	{

		if(n & (1ll << i))

		{

			for(int b = cnt;b <= 63;++b)

			{

				f[b] = (f[b] + c[i][b - cnt]) % PHI;

			}

			++cnt;

		}

	}

	for(int i = 1;i <= 63;++i)ans = (ans * power(i,f[i])) % MOD;

	cout << ans << endl;

	return 0;

}