首页 > 试题广场 >

小红的相等数组

[编程题]小红的相等数组
  • 热度指数：320 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小红希望你构造一个长度为 n 的数组，满足：
1. 数组中的每个元素 a_i 满足 0 \leq a_i < 2^k
2. 数组所有元素的异或和小于等于所有元素的与和。即 a_1 \oplus a_2 \oplus \cdots \oplus a_n \leq a_1 \And a_2 \And \cdots \And a_n

小红想知道有多少种可能的方案数。

输入描述:
第一行输入两个整数 n 和 k。
1 \leq n \leq 10^5
0 \leq k \leq 10^5


输出描述:
输出一个整数，表示满足条件的数组的方案数。由于答案可能很大，请对 10^9 + 7 取模。
示例1

输入

2 2

输出

6

说明

一共有 6 种可能的方案数。分别是 [0,0], [1,1], [2,2], [3,3], [2,3], [3,2]。
算法知识视频讲解
开通博客
头像 丨阿伟丨
发表于 2025-09-12 16:02:44
题目链接 REAL740 小红的相等数组 题目描述 小红希望你构造一个长度为 的数组，满足： 数组中的每个元素 满足 。 数组所有元素的异或和小于等于所有元素的与和。即: 小红想知道有多少种可能的方案数。答案对 取模。 思路分析 1. 问题转换：按位分析 问题的核心约束是 异或和 < 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

位运算 组合数学 阿里云
难度：
1条回答 698浏览

热门推荐

相关试题

小红的相等数组

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号