1000ms

Difficulty: 8

所属公司 : 阿里

时间 :2025年3月16日-阿里云(开发岗)

算法与标签>动态规划

会员专享

请先登录，开通会员或购买该题目所属题库（阿里系机考题库），可解锁完整内容。

购买题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（阿里系机考题库），可解锁完整内容。

购买题库开通会员

题解

题面描述

给定两个整数 $n$ 和 $k$ ，要求构造一个长度为 $n$ 的数组 $[a_1,a_2,\dots,a_n]$ ，满足：

每个元素满足 $0 \le a_i < 2^k$ ；
数组所有元素的异或和 $\oplus_{i=1}^{n} a_i$ 小于等于所有元素的与和 $\&_{i=1}^{n} a_i$ 。

要求统计满足条件的数组方案数，并对 $10^9+7$ 取模。

题目内容

小红希望你构造一个长度为 $n$ 的数组,满足:

$1$ .数组中的每个元素 $a$ 满足 $0≤a_i<2^k$