bzoj3209 花神的数论题 (二进制数位dp)

时间:2021-08-08 11:50:04

二进制数位dp,就是把原本的数字转化成二进制而以,原来是10进制,现在是二进制来做,没有想像的那么难

不知到自己怎么相出来的。。。感觉,如果没有一个明确的思路,就算做出来了,也并不能锻炼自己的能力,因为我现在需要训练的是做题的思维方法啊!

sum(i) 表示 i 的二进制表示中 1 的个数。给出一个正整数 N ,求sum(1)—sum(N) 的乘积。

首先,这道题直接做,感觉无从下手,那么我就想,怎么来转换一下,求1~n中每个数的一的个数总相乘之积,首先感觉到,每个数都会有唯一对应的1的个数,且一的个数的取值只有最多60,因为n最大   10^15,  那么我就想,如果枚举1的个数k,计算有多少个数含有k个1,(因为数位dp就是来做,有多少满足的数,且不关注数的大小)这样就转化为数位dp的模型了

另外,发现含有k个1的数个数可能非常多,快速幂搞一搞啦,

不过快速幂要注意超long long 的情况!!,因为在很多题mod比较大,mod<根号2^31,平方之后就有可能超int!!!!!

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std; typedef long long int ll;
const int MAXN=+;
const ll mod=; ll n,Ans;
ll c[MAXN][MAXN];
int l,wei[MAXN];
void pre()
{
for (int i=;i<=;++i)
c[i][]=;
for(int i=;i<=;i++)
for(int j=;j<=i;++j)
c[i][j]=c[i-][j-]+c[i-][j];//c[i][j]表示i位,j个1。
scanf("%lld",&n);
l=,n+=;//只能计算小于n的个数,所以要加1
while(n)
{
wei[++l]=n&;
n>>=;
}//将n转换为2进制。
}
ll Solve(int x)//解决有x个1的方案数
{
ll sum=;
for (int i=l;i>=;--i)
{
if(wei[i]==)
{
sum+=c[i-][x];
x--;
}
if(x<) break;
}
return sum;
}
ll Pow(ll a, ll b){
ll tot=;
a%=mod;
while(b)
{
if(b&)
{
tot=a*tot%mod;
tot%=mod;
}
b>>=;a*=a;a%=mod;
}
return tot;
}
int main()
{
pre();
Ans=1ll;
for(int i=;i<=l;++i)
Ans=Ans*Pow(i,Solve(i))%mod;
printf("%lld\n",Ans);
return ;
}