【题解】花神的数论题

【P4317】题解

一：【题意】

求f(1)f(2)...*f(n)%mod
f(x)表x二进制上多少个1

二：【解法】

压入状态所需维度
当前位，前导零，数位限制，前面1个数

三：【代码】

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e7+7;
vector<int> a;
int dp[64][2][2][64];
int Dp(int now,int st,int lim,int sum){if(now==a.size()) return max(1ll,sum);if(dp[now][st][lim][sum]!=-1) return dp[now][st][lim][sum];int maxn=lim?a[now]:1;int ans=1;for(int i=0;i<=maxn;i++){ans*=Dp(now+1,st&&(i==0),lim&&(i==maxn),sum+(i==1));ans%=mod;}dp[now][st][lim][sum]=ans;return ans;
}
int dfs(int x){while(x){a.push_back(x&1);x/=2;}reverse(a.begin(),a.end());memset(dp,-1,sizeof dp);return Dp(0,1,1,0);
}
signed main(){int n;cin>>n;cout<<dfs(n)<<"\n";return 0;
}