luogu P4317 花神的数论题 数位dp

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define MAXN 2147483647
#define ll long long

using namespace std;
const int mod=1e7+7;
int len;
ll n;
int a[55];
ll dp[55][55];
ll dfs(int p,int st,int limit)
{
	//如果位数大于总长度，就返回1的个数 或者 是1
	if(p>len)
		return max(st,1);
	if(dp[p][st]!=-1&&!limit)
		return dp[p][st];
	ll ret=1;
	int up=limit?a[len-p+1]:1;
	for(int i=0; i<=up; i++)
		(ret*=dfs(p+1,i==1?st+1:st,limit&&(i==up))%mod)%=mod;
	if(!limit)
		dp[p][st]=ret;
	return ret;
}
int main()
{
	scanf("%lld",&n);
	while(n)
	{
		a[++len]=n&1;
		n>>=1;
	}
	memset(dp,-1,sizeof dp);
	printf("%lld
",dfs(1,0,1));
	return 0;
}