首页 > 试题广场 >

小红的相等数组

[编程题]小红的相等数组
  • 热度指数：385 时间限制：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) 收起
头像 牛客题解官
发表于 2026-03-12 15:29:00
小红的相等数组 [题目链接](https://www.nowcoder.com/practice/d45de1dae26a49bca9d8832b9551737f) 思路 构造长度为 的数组，每个元素在 ，要求所有元素的异或和 不超过与和 。统计方案数，对 取模。 逐位分析 异或和与按位与都是 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

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

热门推荐

相关试题

小红的相等数组

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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