【找规律】ARC 066D Xor Sum AtCoder - 2272
2024-09-27 13:27:55
题目大意
给出一个整数\(n\),已知\(0\le u,v\le n\),求满足\(a\ xor\ b=u\)且\(a+b=v\)的\(a、b\)对数
样例1输入
3
样例1输出
5
/*
u=0,v=0 (Let a=0,b=0, then 0 xor 0=0, 0+0=0.)
u=0,v=2 (Let a=1,b=1, then 1 xor 1=0, 1+1=2.)
u=1,v=1 (Let a=1,b=0, then 1 xor 0=1, 1+0=1.)
u=2,v=2 (Let a=2,b=0, then 2 xor 0=2, 2+0=2.)
u=3,v=3 (Let a=3,b=0, then 3 xor 0=3, 3+0=3.)
*/
样例2输入
1422
样例2输出
52277
样例3输入
1000000000000000000
样例3输出
787014179
思路
用暴力打表,前20个答案分别为1、2、4、5、8、10、13、14、18、21、26、28、33、36、40、41、46、50、57、60、68。
可以发现规律
\(\begin{cases}
a_{2k}=2a_{k-1}+a_k \\
a_{2k-1}=2a_k+a_{k-1} \\
\end{cases}\)
代码
#include <cstdio>
#include <map>
typedef long long ll;
const int Mod=1e9+7;
const int maxn=1000000+5;
using namespace std;
ll a[30]={1,2,4,5,8,10,13,14,18,21,26,28,33,36,40,41,46,50,57,60,68};
map<ll,ll> mp;//记忆化
ll dfs(ll x) {
if(x<=20)
return a[x];
if(mp[x])
return mp[x];
if(x%2)
return mp[x]=(2*dfs(x/2)%Mod+dfs(x/2-1)%Mod)%Mod;
else
return mp[x]=(2*dfs(x/2-1)%Mod+dfs(x/2)%Mod)%Mod;
}
int main() {
ll n;
scanf("%lld",&n);
printf("%lld\n",dfs(n));
return 0;
}
最新文章
- 关于iOS10的允许访问用户数据产生的问题
- MIME Sniffing
- [转]阿里云CentOS配置全过程
- [Tomcat 源码分析系列] (附件) : catalina.bat 脚本
- Selenium Waits
- ipad ------ 与iPhone的差别
- html5 新增语义标签
- hdoj 1257 DP||贪心
- log4j配置文件简要记录
- android自定义Notification通知栏实例
- Xampp相关命令
- 【问题解决】jhipster-registry-master空白页
- sublime text (ST)一篇通(安装、配置、扩展、使用)
- 实现简单的printf函数
- Centos7 Lnmp的环境搭建
- #254 Find the Longest Word in a String
- MySQL log_slave_updates 参数【转】
- 五子棋游戏SRS文档
- day3_元组
- python Trie树和双数组TRIE树的实现. 拥有3个功能:插入,删除,给前缀智能找到所有能匹配的单词