洛谷P4317 花神的数论题题解

题意：

花神的题目是这样的：

设 $S_i$ 表示 $i$ 的二进制表示中 $1$ 的个数。

给出一个正整数 $N$ ，花神要问你 $\prod_{i=1}^{N}S_i$ 模 $10000007$ 的值。

输入格式：

一个正整数 $N$。

输出格式：

一个数，答案模 $10000007$ 的值。

数据范围：

对于 $100\%$ 的数据，$1\le N\le 10^{15}$。

~~数位dp还是写的太少了~~……

注意到 $N$ 不是特别大，大约 $2^{50}$ 左右。

考虑枚举二进制下 $1$ 的个数 $i$ ，并统计 $[1,N]$ 中有多少个这样的数（显然他们的 $S_i$ 是一样的）。

这个可以通过数位dp得到，设有 $k_i$ 个这样的数，则答案为 $\prod_{i=1}^{50} i^{k_i}$

时间复杂度 $\mathcal{O}(\log^4N)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 10000007;
template<typename T> void up(T &x, T y) { x < y ? x = y : 0; }
template<typename T> void down(T &x, T y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(88))

int len, num[N], ans[N], f[N][N][N][2];
int qpow(int a, int b)
{
    int r = 1;
    for(a %= mod; b; b >>= 1, a = a * a % mod)
        if(b & 1) r = r * a % mod;
    return r;
}
int dfs(int u, int st, int tot, bool limit)
{
    if(!u) return st == tot;
    if(~f[u][st][tot][limit]) return f[u][st][tot][limit];
    int up = limit ? num[u] : 1, res = 0;
    rep(i, 0, up) res += dfs(u - 1, st + i, tot, limit && (i == up));
    return f[u][st][tot][limit] = res;
}
int solve(int n)
{
    while(n) { num[++len] = n & 1, n >>= 1; }
    int res = 1;
    rep(i, 1, len)
    {
        memset(f, -1, sizeof(f));
        res = res * qpow(i, dfs(len, 0, i, 1)) % mod;
    }
    return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n; cout << solve(n) << '\n';
    return 0;
}