【洛谷P4317】花神的数论题 | Mrsrz's blog

二进制数位 DP

题目大意：

给定 $n$ ，令 $F(x)$ 表示 $x$ 在二进制下的 $1$ 的个数，求 $\prod_{i=1}^n F(i)$。

题解：

在二进制下进行数位 dp。

令 $f[i][j][t]$ 表示当前考虑了第 $i$ 位之前，有 $j$ 位为 $1$，$t$ 表示之前的位数是否和 $n$ 的前面几位相同。

转移枚举下一位的值。

最后快速幂求乘积即可。

时间复杂度 $O(log^2 n)$。

Code：

#include<iostream>
using namespace std;
typedef long long LL;
const int md=10000007;
#define lg(x)(63-__builtin_clzll(x))
LL n,f[55][55][2];
inline int pow(int a,LL b){
    int ret=1;
    for(;b;b>>=1,a=(LL)a*a%md)
        if(b&1)ret=(LL)ret*a%md;
    return ret;
}
int main(){
    cin>>n;
    int w=lg(n);
    f[w][0][0]=f[w][1][1]=1;
    for(int i=w-1;~i;--i){
        const int wg=n>>i&1;
        for(int c=0;c<=w+1;++c)
            for(int tg=0;tg<2;++tg){
                for(int nx=0;nx<2;++nx){
                    f[i][c+nx][tg&&wg==nx]+=f[i+1][c][tg];
                    if(tg&&wg==nx)break;
                }
            }
    }
    int ans=1;
    for(int i=1;i<=w+1;++i)
        ans=(LL)ans*pow(i,f[0][i][0]+f[0][i][1])%md;
    cout<<ans<<endl;
    return 0;
}