当前位置:网站首页>暑假第一周
暑假第一周
2022-07-05 08:31:00 【Alex Su (*^▽^*)】
D. Infinite Set(二进制+dp)
关键是看成二进制,乘以4相当于补两个0,乘2加1相当于补一个1
dpi表示二进制表示长度为i的方案数,那么有dpi = dpi-1+dpi-2
那么考虑怎么处理已经有的数
首先要去掉一些重复的数,也就是一个数如果能被另一个数生成,就去掉
这个很好处理,就暴力枚举当前数可能由哪些数生成,然后用map看是否是已经有的数即可
那么用gi表示原本就已经有的数长度为i的有多少个
那么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;
}
边栏推荐
- Agile project management of project management
- Arduino operation stm32
- Negative pressure generation of buck-boost circuit
- 2020-05-21
- 2022.7.4-----leetcode.1200
- MySQL MHA high availability cluster
- 猜谜语啦(8)
- Esphone retrofits old fans
- [NAS1](2021CVPR)AttentiveNAS: Improving Neural Architecture Search via Attentive Sampling (未完)
- Esphone Feixun DC1 soft change access homeassstant
猜你喜欢
每日一题——替换空格
【三层架构及JDBC总结】
Several implementation schemes of anti reverse connection protection of positive and negative poles of power supply!
猜谜语啦(10)
Example 010: time to show
[three tier architecture]
On boost circuit
Design a clock frequency division circuit that can be switched arbitrarily
UE pixel stream, come to a "diet pill"!
Classic application of MOS transistor circuit design (1) -iic bidirectional level shift
随机推荐
[paper reading] the latest transfer ability in deep learning: a survey in 2022
FIO测试硬盘性能参数和实例详细总结(附源码)
[cloud native | learn kubernetes from scratch] III. kubernetes cluster management tool kubectl
What are the test items of power battery ul2580
Working principle and type selection of common mode inductor
NTC thermistor application - temperature measurement
PIP installation
Take you to understand the working principle of lithium battery protection board
Example 002: the bonus paid by the "individual income tax calculation" enterprise is based on the profit commission. When the profit (I) is less than or equal to 100000 yuan, the bonus can be increase
Go dependency injection -- Google open source library wire
Agile project management of project management
实例003:完全平方数 一个整数,它加上100后是一个完全平方数,再加上168又是一个完全平方数,请问该数是多少?
Synchronization of QT multithreading
[nas1] (2021cvpr) attentivenas: improving neural architecture search via attentive sampling (unfinished)
STM32 single chip microcomputer - bit band operation
Example 006: Fibonacci series
Esp8266 interrupt configuration
Summary of SIM card circuit knowledge
实例002:“个税计算” 企业发放的奖金根据利润提成。利润(I)低于或等于10万元时,奖金可提10%;利润高于10万元,低于20万元时,低于10万元的部分按10%提成,高于10万元的部分,可提成7.
猜谜语啦(11)