[BZOJ3209]花神的数论题（数位dp）

题目描述

传送门

题目大意：sum(i)表示i的二进制中1的个数，求 ∏i=1nsum(i)

题解

问题转化为有多少个数二进制中1的个数为i f(i,0/1,j)表示二进制为i位数，是否卡上界，有j个1的数的个数 dp完了之后快速幂一下就行了

代码

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; #define LL long long #define Mod 10000007 LL num,ans; int n,dig[100]; LL f[100][2][100],cnt[100]; int calc(LL x) { int ans=0; while (x) dig[++ans]=x&1,x>>=1; for (int i=1;i<=ans>>1;++i) swap(dig[i],dig[ans-i+1]); return ans; } LL fast_pow(LL a,LL p) { LL ans=1LL; for (;p;p>>=1LL,a=a*a%Mod) if (p&1LL) ans=ans*a%Mod; return ans; } int main() { scanf("%lld",&num); n=calc(num); f[1][0][0]=f[1][1][1]=1LL; for (int i=1;i<n;++i) for (int j=0;j<=1;++j) for (int k=0;k<=i;++k) { int lim=j?dig[i+1]:1; LL now=f[i][j][k]; for (int p=0;p<=lim;++p) f[i+1][(j&&p==dig[i+1])?1:0][p?k+1:k]+=now; } for (int j=0;j<=1;++j) for (int k=1;k<=n;++k) cnt[k]+=f[n][j][k]; ans=1LL; for (int i=1;i<=n;++i) ans=ans*fast_pow(i,cnt[i])%Mod; printf("%lld\n",ans); }