博客

题意：给你一个数N，求出[1,N]中所有的数的二进制中1的个数的连乘。

刚开始看到这道题DP状态都不太好找，但因为之前做过洛谷的另一道“同类分布”的题，后来就有了点思路。

因为这道题DP状态不太好定义，不太好保存状态，所以我们可以枚举1出现的所有次数，对应出现的个数，例如，1出现的次数为k，数位DP出[1,N]内所以1次数为k的数，设其总数为num，则对应答案就是k

^num

。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int mod=10000007;
ll dp[70][2][70];		//dp[pos][limit][sum]表示枚举到第pos位时，是否达到上限，此时1出现的次数为sum
int digit[70];

ll dfs(int pos,int sum,int all,int limit)		//all表示1出现的总次数（要枚举出来）
{
	if(pos==-1)	return sum==all? 1:0;
	if(dp[pos][limit][sum]!=-1)	return dp[pos][limit][sum];
	ll ret=0;
	int up= limit? digit[pos]:1;
	for(int i=0;i<=up;i++)
		ret=ret+dfs(pos-1,sum+(i==1),all,limit&&i==digit[pos]);
	return dp[pos][limit][sum]=ret;
 } 

ll q_pow(ll x,ll y)
{
	ll ret=1;
	while(y)
	{
		if(y&1)	ret=ret*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return ret;
}
 
ll solve(ll n)
{
	int pos=0;
	while(n)	digit[pos++]=n%2, n/=2;
	ll ans=1;
	for(ll i=1;i<=pos;i++)
	{
		memset(dp,-1,sizeof(dp));
		ans=ans*q_pow(i,dfs(pos-1,0,i,1))%mod;
	}
	return ans%mod;
}

int main()
{
	ll n;
	cin>>n;
	cout<<solve(n)<<endl;
	return 0;
}