题目 3372:

蓝桥杯2026年第十七届省赛真题-星光共鸣

 时间限制: 1s 内存限制: 128MB

题目描述

小蓝是一名星际探险家。在一次遗迹探索中,他发现了一块 “星光石板”。

石板上从左到右一共有 N 个凹槽。对于每个凹槽,小蓝都可以选择嵌入一颗 “星之碎片”,记作 1;也可以保持空置,记作 0。这样一来,整块石板的状态就可以用一个长度为 N 的 01 串来表示。

根据遗迹的记载,石板会对 “连续且完整的碎片段” 产生共鸣。具体地,对于任意一个连续子区间 [l, r](1 ≤ l ≤ r ≤ N),如果这一段对应的凹槽全部都嵌入了碎片,也就是区间内每一位都是 1,那么这个区间就会产生一次 “星光共鸣”。反之,只要其中出现过一个 0,这段区间就不会产生共鸣。

因此,一种填充方案所产生的 “星光共鸣总次数”,就等于它的 01 串中 “全为 1 的连续子区间” 的数量。

例如,当 N =4,石板状态为 1101 时:

• [1, 1]、[2, 2]、[4, 4] 对应 1,各产生 1 次共鸣;

• [1, 2] 对应 11,再产生 1 次共鸣;

• 其他子区间如 [2, 3] 对应 10、[3, 4] 对应 01,这样的区间包含 0,不会产生共鸣。

所以该状态一共产生了 4 次共鸣。

现在,小蓝打算枚举所有可能的填充方案。由于每个凹槽只有放与不放两种选择,总共有 2N 种不同的 01 串。小蓝想知道:在这些方案中,有多少种方案的共鸣总次数至少为 K?

由于答案可能很大,请输出满足条件的方案数对 109 +7 取模后的结果。


输入格式

输入仅一行,包含两个整数 N 和 K,表示石板上的凹槽数量,以及要求达到的最少 “星光共鸣” 次数。


输出格式

输出一个整数,表示满足 “星光共鸣总次数不少于 K” 的状态数量。由于答案可能很大,请输出对 109 +7 取模后的结果。


样例输入

4 4

样例输出

5

提示

【样例说明】

当 N =4、K =4 时,共有 5 种状态满足条件,分别为:

• 1110:共鸣次数为 3+ 2 + 1 = 6 ≥ 4;

• 1101:共鸣次数为 (2 + 1) + 1 = 4 ≥ 4;

• 1011:共鸣次数为 1+ (2 + 1) = 4 ≥ 4;

• 0111:共鸣次数为 6 ≥ 4;

• 1111:共鸣次数为 4+ 3 + 2 + 1 = 10 ≥ 4。

所以答案为 5。

【评测用例规模与约定】

对于 30% 的数据,保证 N ≤ 12;

对于 100% 的数据,保证 1 ≤ N ≤ 1000,0 ≤ K ≤ min( N(N+1)/2 , 100)。

标签