位运算+线性dp
2023-04-18 15:35:15 时间
题目链接
由范围是2的p次方(p<2*10^5)
范围太大了
往位运算方面想
a数组集合都在S集合里面,由a数组元素衍生S中元素
- x=2y+1
转变成位运算就是左移一位末尾加一
- x=4y
转变成位运算就是左移两位
思路
找a中每个数的根源————往下找
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define endl " " const int N = 2e5; const int MOD = 1e9 + 7; ll f[N + 1]; int main() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); int n, p; cin >> n >> p; vector<ll>a(n + 1); for (int i = 1; i <= n; i++)cin >> a[i]; map<ll, bool>vis; f[1] = 1; f[0] = 0; f[2] = 2; for (int i = 3; i <= N; i++) { f[i] = (f[i - 1] + f[i - 2])%MOD; } for (int i = 1; i <= N; i++)f[i] = (f[i - 1] + f[i]) % MOD; sort(a.begin() + 1, a.end()); ll ans = 0; for (int i = 1; i <= n; i++) { ll t = a[i]; bool ok = true; while (t) { if (vis[t])ok = false; if (t & 1)t >>= 1; else if (t % 4 == 0)t >>= 2; else break; } if (!ok)continue; ll len = (ll)log2(a[i]) + 1LL; if(p>=len) ans =(ans+ f[max(0LL, (ll)p - len)]+1)%MOD; vis[a[i]] = true; } cout << ans << endl; return 0; }
相关文章
- Excel批量xls转xlsx工具
- Power Query日期格式转换
- Python3.7将普通图片(png)转换为SVG图片格式并且让你的网站Logo(图标)从此”动”起来
- Swift 比较运算和三目条件运算
- Power BI做一个日历图表
- Electron基础 Hello,World!
- Swift 字符串和字符
- 灵活的模式发现和分析(CS)
- 成为更好的 Swift 开发者的 10 个 Tips(译)
- 神级程序员都在用什么工具?【建议收藏】
- 面试官再问你 ThreadLocal,你就这样“怼”回去!
- Swift 如何使用 Access Control
- Typecho主题Brave—勇敢爱
- 到底什么是重入锁?拜托,一次搞清楚!
- Koa 源码研读
- 在越狱后的iOS上运行QEMU虚拟机~
- 10分钟搞定Dubbo集成Spring Boot ,实现多注册中心
- 使用 SRI 解决 CDN 劫持
- 使用 requestAnimationFrame 解决滚动点停误触和 scroll 事件延迟
- webpack 从入门到放弃