当前位置:网站首页>The first week of summer vacation
The first week of summer vacation
2022-07-05 08:33:00 【Alex Su (*^▽^*)】
D. Infinite Set( Binary system +dp)
The key is to look at binary , multiply 4 Equivalent to two 0, ride 2 Add 1 It's equivalent to adding one 1
dpi Indicates that the binary indicates that the length is i Number of alternatives , So there are dpi = dpi-1+dpi-2
Then consider how to deal with the existing numbers
First, remove some duplicate numbers , That is, if one number can be generated by another number , Just remove
This is very easy to handle , Enumerate which numbers the current number may be generated by , And then use map See if it's the number you already have
Then use gi It means that the length of the existing number is i How many
that dpi = dpi + dpi-1 + gi
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
int a[N], dp[N], g[N], n, p;
unordered_map<int, int> mp;
int len(int x)
{
int res = 0;
while(x) res++, x >>= 1;
return res;
}
bool check(int x)
{
while(x)
{
if(x % 4 == 0)
{
x /= 4;
if(mp[x]) return false;
}
else if((x - 1) % 2 == 0)
{
x = (x - 1) / 2;
if(mp[x]) return false;
}
else break;
}
return true;
}
int main()
{
scanf("%d%d", &n, &p);
_for(i, 1, n) scanf("%d", &a[i]), mp[a[i]] = 1;
_for(i, 1, n)
if(check(a[i]))
g[len(a[i])]++;
dp[1] = g[1];
_for(i, 2, p)
dp[i] = (dp[i - 1] + dp[i - 2] + g[i]) % mod;
int ans = 0;
_for(i, 1, p) ans = (ans + dp[i]) % mod;
printf("%d\n", ans);
return 0;
}
边栏推荐
- Explore the authentication mechanism of StarUML
- 每日一题——输入一个日期,输出它是该年的第几天
- Anonymous structure in C language
- UE像素流,来颗“减肥药”吧!
- 剑指 Offer 05. 替换空格
- [nas1] (2021cvpr) attentivenas: improving neural architecture search via attentive sampling (unfinished)
- PIP installation
- Xrosstools tool installation for X-Series
- MySQL之MHA高可用集群
- MySQL之MHA高可用集群
猜你喜欢
Brief discussion on Buck buck circuit
Management and use of DokuWiki (supplementary)
leetcode - 445. Add two numbers II
Business modeling of software model | object modeling
猜谜语啦(5)
实例001:数字组合 有四个数字:1、2、3、4,能组成多少个互不相同且无重复数字的三位数?各是多少?
Example 007: copy data from one list to another list.
Low code platform | apaas platform construction analysis
Several implementation schemes of anti reverse connection protection of positive and negative poles of power supply!
Bluebridge cup internet of things competition basic graphic tutorial - clock selection
随机推荐
What are the test items of power battery ul2580
轮子1:QCustomPlot初始化模板
2022.7.4-----leetcode. one thousand and two hundred
实例009:暂停一秒输出
暑假第一周
Sword finger offer 05 Replace spaces
Anonymous structure in C language
Weidongshan Internet of things learning lesson 1
Example 005: three numbers sorting input three integers x, y, Z, please output these three numbers from small to large.
Shell script realizes the reading of serial port and the parsing of message
Old Wang's esp8266 and old Wu's ws2818 light strip
Classic application of MOS transistor circuit design (1) -iic bidirectional level shift
Summary of SIM card circuit knowledge
leetcode - 445. Add two numbers II
猜谜语啦(7)
leetcode - 445. 两数相加 II
[noi simulation] juice tree (tree DP)
实例010:给人看的时间
Google sitemap files for rails Projects - Google sitemap files for rails projects
Take you to understand the working principle of lithium battery protection board