您当前的位置: 首页 >  动态规划

MangataTS

暂无认证

  • 0浏览

    0关注

    423博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

Codeforces Round #772 (Div. 2) D. Infinite Set (动态规划+思维)

MangataTS 发布时间:2022-03-03 21:07:44 ,浏览量:0

题目链接

https://codeforces.com/contest/1635/problem/D

题面

在这里插入图片描述

题意

输入一个n表示数组 a a a 的长度,然后输入一个 p,然后输入n个不同的元素,问在 [ 0 , 2 p ] [0,2^p] [0,2p]范围内有多少数 x x x 满足下列其中至少一种条件,包含满足条件的集合为 S S S :

    1. x = a i x=a_i x=ai​ 在数组中
    1. x = 2 × y + 1 x=2\times y + 1 x=2×y+1 并且 y y y 在 S S S 中
    1. x = 4 × y x=4\times y x=4×y 并且 y y y 在 S S S 中

输出满足条件的个数,并对 1 0 9 + 7 10^9+7 109+7 取模

思路

我们来观察这三种条件:

  • 对于第一种条件,表示我们基础的 S S S 集合
  • 对于第二种条件,我们会发现就是将其二进制下的位数末尾添加了一个 1
  • 对于第三种条件,我们会发现其实就是将其二进制的位数末尾添加了两个 0

我们再对 2 p 2^p 2p 转化为二进制实际上就是一个小于等于 p p p 个2的二进制数,那么我们就可以将问题转化为某个数的二进制长度的方案数,由于我们的两种操作一种是增加一位,另一种是增加两位,那么长度数量的状态转移方程就是 f [ i ] = f [ i − 1 ] + f [ i − 2 ] f[i] = f[i-1] + f[i-2] f[i]=f[i−1]+f[i−2] 也就是一个斐波那契数列,那么对于一个数 x x x 其延申长度小于 p p p 位的时候有 ∑ i = 1 p − l e n ( x ) f [ i ] \sum_{i=1}^{p-len(x)}{f[i]} ∑i=1p−len(x)​f[i] 这么多种,但是如果我们直接对每一个数进行这样计算的话是不行的,因为有重复的情况,所所以我们开一个 m a p map map ,记录我们是否以及对这个数进行了计算,详情请看代码

代码
#include
using namespace std;

#define ll long long 

#define mod 1000000007

const int N = 2e5 + 10;

ll a[N],n,p,f[N]={0,1,2};


void slove(){
	cin>>n>>p;
	for(int i = 1;i >a[i];
	sort(a+1,a+1+n);
	map vis;
	ll ans = 0;
	for(int i = 1;i >= 1;//如果是奇数,那么说明是2y+1
			else if(k % 4 == 0) k >>= 2;//如果是4的倍数,那么说明是4y
			else break;//如果上述两种情况都不算,那么说明此时不能延申
		}
		if(!fg) continue;
		ll len = (ll)log2(a[i]) + 1LL;
		if(p >= len)
			ans = (ans + f[max(0LL,p-len)] + 1) % mod;
		vis[a[i]] = true;
	}
	cout            
关注
打赏
1665836431
查看更多评论
0.0391s