定义\(sum(i)\)表示\(i\)在二进制下\(1\)的个数

求\(\prod_{i=1}^{n}sum(i)\)

暴力非常\(sb\)显然可以随便写，但是显然也是会\(T\)

于是我们换个思路

我们设\(tot\)表示\(sum(i)=x\)的\(i\)有多少个，于是答案就是\(x^{tot}\)

我们枚举\(x\)就行了，\(x\)显然不会很大，也就是\(log_2{n}\)

之后就可以开始数位\(dp\)了

我们设\(dp[i][0/1][j]\)表示最高位填到第\(i\)位，其中最高位填\(0/1\)，一共填了\(j\)个1一共有多少个数

方程很显然，就是往最高位上填\(0/1\)

填0的话

\[dp[i+1][0][j]+=dp[i][1][j]+dp[i][0][j]\]

填1的话

\[dp[i+1][1][j+1]+=dp[i][0][j]+dp[i][1][j]\]

之后我们按照数位\(dp\)的套路来做就行了

代码

#include
    
     #include
     
      #include
      
       #define LL long long #define re register#define maxn 55const LL mod=10000007;const LL P=9988440;LL n;int a[maxn];LL dp[maxn][2][maxn];inline LL quick(LL a,LL b){    LL S=1;    while(b)    {        if(b&1) S=S*a%mod;        b>>=1ll;        a=a*a%mod;    }    return S;}inline LL sum(LL x){    LL cnt=0;    while(x)    {        if(x&1ll) cnt++;        x>>=1ll;    }    return cnt;}inline LL slove(LL x){    int num=0;    while(x)    {        ++num;        if(x&1ll) a[num]=1;        x>>=1ll;    }//分解数位    dp[1][1][1]=1;    dp[1][0][0]=1;    for(re int i=1;i
       
        =1;i--)//之后我们卡前面的[i+1,num]为完全相等，让第i位小于n的第i位，我们就可以让后面的位数随便填了        {            for(re int j=0;j