日常废话：
完了高一开学第二天作业就写不完了药丸（其实第一天就写不完了）
显然爆搜肯定过不了这道题但是有60分
我们注意到在[1,n]中，有着相同的1的个数的数有很多。若有x个数有i个1，则对答案产生的贡献是(i^x)。考虑到(nleq10^{50}),所以最多只有50个1，看起来能够接受。这样问题就转化成求1~n内，二进制表示中有i个1的数的个数，可以用数位dp求。
关于(i^x),用快速幂搞一搞就好了。
数位dp
using namespace std;
typedef long long ll;
const int inf=214748364;
const ll mod=10000007;
inline ll read()
{
char ch=getchar();
ll x=0;bool f=0;
while(ch<'0'||ch>'9')
{
if(ch=='-')f=1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?-x:x;
}
int li[60],t;
ll n,ans,f[60],g[60][60][60];//f[i]表示[1,n]中有i的1的个数，g[i][j][h]表示填到第i位，当前总共有j个1，当前要求的1的个数是h,数的个数
ll ksm(ll a,ll b)//注意a,b都是longlong
{
ll r=1;
while(b)
{
if(b&1)r=(r*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return r%mod;
}
ll dfs(int now,int cnt,int goal,bool lim)
{
if(!now) return cnt==goal;
if(!lim&&g[now][cnt][goal]!=-1) return g[now][cnt][goal];//这里初始化为-1比初始化为0要省时间的多
int up=lim?li[now]:1;
ll rtn=0;
for(int i=0;i<=up;i++)
{
bool lli=(i==up);
lli&=lim;
rtn+=dfs(now-1,cnt+i,goal,lli);
}
if(!lim)g[now][cnt][goal]=rtn;
return rtn;
}
int main()
{
n=read();
while(n)
{
li[++t]=n%2;
n/=2;
}
memset(g,-1,sizeof(g));
for(int i=1;i<=t;i++)
f[i]=dfs(t,0,i,1);
ans=1;
for(int i=1;i<=t;i++)
{
ll kk=ksm(i,f[i]);
ans=((ans%mod)*(kk%mod))%mod;
}
printf("%lld",ans);
}
接下来就与此题正解无瓜了
纪念一个写歪了的dfs
如果在这题里面考虑爆搜，如何做到纯O(n)的爆搜
若我们从1循环到n，每个用logn的时间看有几个1，复杂度是O(nlogn)。
我们参照数位dp的填数的思想，枚举每一位填的是啥。填到最后，有cnt个1，则f[cnt]++。这样一共是n个数会被枚举到，所以是O(n)的。
实测比上面的g数组初始化为0的写法多10分
写歪了的dfs
using namespace std;
typedef long long ll;
const int inf=214748364;
const ll mod=10000007;
inline ll read()
{
char ch=getchar();
ll x=0;bool f=0;
while(ch<'0'||ch>'9')
{
if(ch=='-')f=1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?-x:x;
}
int li[60],t;
ll n,ans,f[60];
ll ksm(ll a,ll b)
{
ll r=1;
while(b)
{
if(b&1)r=(r*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return r%mod;
}
void dfs(int now,int cnt,bool lim)
{
if(!now){f[cnt]++;return;}
int up=(lim)?li[now]:1;
for(int i=0;i<=up;i++)
dfs(now-1,cnt+i,li&&(i==up));
}
int main()
{
n=read();
while(n)
{
li[++t]=n%2;
n/=2;
}
dfs(t+1,0,1);
ans=1;
for(int i=1;i<=t;i++)
{
ll kk=ksm(i,f[i]);
ans=((ans%mod)*(kk%mod))%mod;
}
printf("%lld",ans);
}
include被我吃了