[Bzoj3209]花神的数论题(数位dp)
2024-09-05 14:20:37
3209: 花神的数论题
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 2633 Solved: 1182
[Submit][Status][Discuss]
Description
背景
众所周知,花神多年来凭借无边的神力狂虐各大 OJ、OI、CF、TC …… 当然也包括 CH 啦。
描述
话说花神这天又来讲课了。课后照例有超级难的神题啦…… 我等蒟蒻又遭殃了。
花神的题目是这样的
设 sum(i) 表示 i 的二进制表示中 1 的个数。给出一个正整数 N ,花神要问你
派(Sum(i)),也就是 sum(1)—sum(N) 的乘积。
Input
一个正整数 N。
Output
一个数,答案模 10000007 的值。
Sample Input
样例输入一
Sample Output
样例输出一
HINT
对于样例一,1*1*2=2;
数据范围与约定
对于 100% 的数据,N≤10^15
Source
然后我们发现不能一起转移,但我们可以求出<=N中 1的个数为k的所有数
最终答案就是。
关于dfs那个转移,就是很裸的模板题,看代码即可。
AC代码:
# include <iostream>
# include <cstdio>
# include <cstring>
using namespace std;
typedef long long LL;
const LL mod = ;
LL f[][],n;int data[],len;
LL dfs(int now,int num,bool lim,bool first)
{
if(num < )return ;
if(!now)return !num;
if(!lim && !first && f[now][num] != -)return f[now][num];
LL ret = ;int p = lim ? data[now] : ;
for(int i = ;i <= p;i++)
ret += dfs(now - ,num - i,lim && i == p,first && !i);
if(!lim && !first)f[now][num] = ret;
return ret;
}
LL cmd(LL k,LL x)
{
LL c = ;
while(k)
{
if(k & 1LL)c = c * x % mod;
x = x * x % mod;
k >>= 1LL;
}
return c;
}
LL calc(LL k)
{
memset(f,-,sizeof f);
len = ;
while(k)data[++len] = k % ,k /= ;
LL ret = ;
for(int i = ;i <= len;i++)
ret = ret * cmd(dfs(len,i,true,true),i) % mod;
return ret;
}
int main()
{
scanf("%lld",&n);
printf("%lld\n",calc(n));
}
最新文章
- winform学习笔记02
- C# 关于DataGridView 绑定数据源时列名窜位置 的处理
- 【Android开发坑系列】之事件
- Redis(7)Creating and Using Cluster Mode
- django中外键关联表的查询随笔
- activity+fragment多次切换出现页面空白问题
- Bootstrap_排版_列表
- awk的接口实现方案1
- 集合的实现 -- 数据结构与算法的javascript描述 第九章
- HTML5之画布的拖拽/拖放
- .NET 使用 MySql.Data.dll 动态库操作MySql的帮助类--MySqlHelper
- Android -- 从源码的角度一步步打造自己的TextView
- Nginx的location匹配规则
- java基础 (四)之集合
- 查看tomcat运行日志
- jqgrid 选中行触发编辑,切换下一行时验证和异步保存上一行数据
- 放假前来个笑话:IT人士群聚喝酒的讲究(超级搞笑)
- POJ 3481 treap
- python——脚本和print
- 手机防盗之获取手机经纬度(Android)
热门文章
- ubuntu下php安装目录说明
- ssm框架搭建(上)
- 洛谷 P1918 保龄球
- 使用JavaScript将当前页面保存成PDF,支持图片和文字的保存
- jquery.placeholder.min.js让吃屎的IE浏览器支持placeholder去吧
- Windows虚拟桌面
- SQL Server数据库的除法默认向下取整,要返回小数的解决方法
- url跳转路径参数获取
- Vickers Vane Pump - Hydraulic Vane Pump Failure: Cavitation, Mechanical Damage
- TWaver可视化编辑器的前世今生(三)Doodle编辑器