题目地址：洛谷：【P4317】花神的数论题 – 洛谷、BZOJ：Problem 3209. — 花神的数论题

题目描述

话说花神这天又来讲课了。课后照例有超级难的神题啦…… 我等蒟蒻又遭殃了。
花神的题目是这样的
设 sum(i) 表示 i 的二进制表示中 1 的个数。给出一个正整数 N ，花神要问你Π(sum(i)),也就是 sum(1)—sum(N) 的乘积。

输入输出格式

输入格式：
一个正整数 N。

输出格式：
一个数，答案模 10000007 的值。

输入输出样例

输入样例#1：

3

输出样例#1：

2

说明

对于样例一，1*1*2=2；
数据范围与约定
对于 100% 的数据，N≤10^15

题解

枚举二进制中含有多少个1，我们可以用数位DP处理出这种情况的方案数，然后快速幂算出结果，乘进答案中。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 60, MO = 10000007;

inline LL fpow(LL n, LL k) {
    LL res = 1;
    while(k) {
        if(k & 1) res = (res * n) % MO;
        n = n * n % MO;
        k >>= 1;
    }
    return res;
}

LL n, dp[MAXN][MAXN][MAXN][2], res[MAXN];
int m, num[MAXN];

inline LL dfs(int step, int cnt, int tot, bool lim) {
    if(!step) return cnt == tot;
    if(dp[step][cnt][tot][lim] != -1) return dp[step][cnt][tot][lim];
    LL res = 0; int limm = lim ? num[step] : 1;
    for(int i = 0; i <= limm; i++) {
        res += dfs(step - 1, cnt + (i == 1), tot, lim && i == limm);
    }
    return dp[step][cnt][tot][lim] = res;
}

int main() {
    memset(dp, -1, sizeof(dp));
    n = readint();
    while(n) {
        num[++m] = n & 1; n >>= 1;
    }
    for(int i = 1; i <= m; i++) {
        res[i] = dfs(m, 0, i, true);
    }
    LL ans = 1;
    for(int i = 1; i <= m; i++) {
        ans = ans * fpow(i, res[i]) % MO;
    }
    printf("%lld", ans);
    return 0;
}