洛谷 P4317 花神的数论题

admin2024-05-15  0

花神的数论题

题目背景

众所周知,花神多年来凭借无边的神力狂虐各大 OJ、OI、CF、TC …… 当然也包括 CH 啦。

题目描述

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

输入格式

一个正整数 N N N

输出格式

一个数,答案模 10000007 10000007 10000007 的值。

样例 #1

样例输入 #1

3

样例输出 #1

2

提示

对于 100 % 100\% 100% 的数据, 1 ≤ N ≤ 1 0 15 1\le N\le 10^{15} 1N1015

算法:数位dp

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int mod = 1e7 + 7;

int dp[56][56];                                     // dp记录[pos][cnt1]状态下对答案的贡献
int a[56];                                          // a[]记录二进制串
int dfs(int pos, int cnt1, bool bound, bool lead_0) // pos为此时的位置,cnt1为前面1的数量,bound表示前面每一位是否都是上界,lead_0表示是否前面全是0
{
    if (pos == 0) // 枚举完每一位时返回
    {
        if (lead_0 == 1) // 如果此时lead_0为1,说明该数为0,则返回1(即返回无效贡献)
            return 1;
        else
            return cnt1;
    }
    if (!bound && dp[pos][cnt1] != -1) // 读取记忆(doge
        return dp[pos][cnt1];
    int max_num; // 可枚举的该位的数的上界
    if (bound)
        max_num = a[pos];
    else
        max_num = 1;
    int res = 1;
    for (int i = 0; i <= max_num; i++)
    {
        if (lead_0 && i == 0)
            res = (1LL * res * dfs(pos - 1, 0, bound && (i == a[pos]), 1)) % mod;
        else
            res = (1LL * res * dfs(pos - 1, cnt1 + (i == 1), bound && (i == a[pos]), 0)) % mod;
    }
    if (!bound && !lead_0) // 没在边界时,记录下该状态对应的答案,记忆化
        dp[pos][cnt1] = res;
    return res;
}
int solve(ll x)
{
    memset(dp, -1, sizeof(dp)); // 将dp数组初始化为-1,表示对应状态的答案目前还未计算出
    int len = 0;
    while (x)
    {
        a[++len] = x % 2;
        x /= 2;
    }
    return dfs(len, 0, 1, 1);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll x;
    cin >> x;
    cout << solve(x);

    return 0;
}
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!