思路

• 设 $L=r-1$。若 $L \ge n$，限制无效，答案为 $2^n \bmod M$（其中 $M=10^9+7$）。

• 令 $f[i]$ 为长度为 $i$ 的合法串数量。

  • 初值：对 $0 \le i \le L$，有 $f[i]=2^i$。

  • 递推：当 $i \ge L+1$（即 $i \ge r$），

    $$f[i] = \sum_{t=1}^{r} f[i-t]$$

• 滑动窗口优化求和：令

  $$W = \sum_{k=0}^{r-1} f[k]$$

  则对 $i \ge r$，有 $f[i]=W$，并维护

  $$W \leftarrow (W + f[i] - f[i-r]) \bmod M$$

• 边界：当 $r=1$ 时，不能出现 $1$，答案恒为 $1$，上述转移同样成立。

• 复杂度：单测 $O(n)$，所有数据总计 $O(\sum n)\le O(10^3)$。

C++

#include <bits/stdc++.h>
using namespace std;

static const long long MOD = 1000000007LL;

// 快速幂：计算 a^e mod MOD
long long modpow(long long a, long long e) {
	long long r = 1 % MOD;
	a %= MOD;
	while (e > 0) {
		if (e & 1) r = (r * a) % MOD;
		a = (a * a) % MOD;
		e >>= 1;
	}
	return r;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	if (!(cin >> T)) return 0;
	while (T--) {
		int n;
		long long r;
		cin >> n >> r;
		long long L = r - 1; // 允许的最大连续1长度
		if (L >= n) {
			// 限制无效，答案为 2^n
			cout << modpow(2, n) << "\n";
			continue;
		}
		// 需要按递推计算
		vector<long long> f(n + 1, 0);
		f[0] = 1; // 空串
		// 预处理 0..L 上的 2^i
		long long pw = 1;
		for (int i = 1; i <= (int)L; ++i) {
			pw = (pw * 2) % MOD;
			f[i] = pw; // f[i] = 2^i
		}
		// 注意 f[0] 需要是 2^0=1，已设
		// 计算初始窗口 W = sum_{k=0..r-1} f[k]，其中 r = L+1
		int R = (int)r; // 窗口宽度
		long long W = 0;
		for (int k = 0; k <= (int)L; ++k) {
			long long val = (k == 0 ? f[0] : f[k]);
			// f[0] 已是 1，f[1..L] 已是 2^i
			if (k == 0 && f[0] == 0) val = 1; // 保护（理论不会触发）
			W += (k == 0 ? f[0] : f[k]);
			if (W >= MOD) W -= MOD;
		}
		// 递推 i = r..n
		for (int i = R; i <= n; ++i) {
			f[i] = W;
			W += f[i];
			if (W >= MOD) W -= MOD;
			W -= f[i - R];
			if (W < 0) W += MOD;
		}
		cout << f[n] % MOD << "\n";
	}
	return 0;
}

Python

import sys

MOD = 10**9 + 7

def modpow(a: int, e: int, m: int = MOD) -> int:
	# 快速幂
	res = 1 % m
	a %= m
	while e > 0:
		if e & 1:
			res = (res * a) % m
		a = (a * a) % m
		e >>= 1
	return res

def solve():
	data = sys.stdin.read().strip().split()
	it = iter(data)
	T = int(next(it))
	out = []
	for _ in range(T):
		n = int(next(it))
		r = int(next(it))
		L = r - 1
		if L >= n:
			out.append(str(modpow(2, n)))
			continue
		# 递推
		f = [0] * (n + 1)
		f[0] = 1
		pw = 1
		for i in range(1, L + 1):
			pw = (pw * 2) % MOD
			f[i] = pw
		R = r
		W = 0
		for k in range(0, L + 1):
			W = (W + f[k]) % MOD
		for i in range(R, n + 1):
			f[i] = W
			W = (W + f[i] - f[i - R]) % MOD
		out.append(str(f[n] % MOD))
	print("\n".join(out))

if __name__ == "__main__":
	solve()

Java

import java.io.*;
import java.util.*;

public class Main {
	static final long MOD = 1_000_000_007L;

	// 快速幂：a^e mod MOD
	static long modpow(long a, long e) {
		long r = 1 % MOD;
		a %= MOD;
		while (e > 0) {
			if ((e & 1) == 1) r = (r * a) % MOD;
			a = (a * a) % MOD;
			e >>= 1;
		}
		return r;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine().trim());
		for (int _case = 0; _case < T; _case++) {
			String line;
			// 读取直到拿到两个整数
			while (true) {
				line = br.readLine();
				if (line == null) return;
				line = line.trim();
				if (!line.isEmpty()) break;
			}
			StringTokenizer st = new StringTokenizer(line);
			int n = Integer.parseInt(st.nextToken());
			long r = Long.parseLong(st.nextToken());
			long L = r - 1;
			if (L >= n) {
				sb.append(modpow(2, n)).append('\n');
				continue;
			}
			long[] f = new long[n + 1];
			f[0] = 1; // 空串
			long pw = 1;
			for (int i = 1; i <= (int)L; i++) {
				pw = (pw * 2) % MOD;
				f[i] = pw;
			}
			int R = (int)r;
			long W = 0;
			for (int k = 0; k <= (int)L; k++) {
				W += f[k];
				if (W >= MOD) W -= MOD;
			}
			for (int i = R; i <= n; i++) {
				f[i] = W;
				W += f[i];
				if (W >= MOD) W -= MOD;
				W -= f[i - R];
				if (W < 0) W += MOD;
			}
			sb.append(f[n] % MOD).append('\n');
		}
		System.out.print(sb.toString());
	}
}

题目内容

【引用开始】

在若干链路层协议中(如 HDLC)，帧边界由标志字段确定。为便于理论分析，约定标志字段为一段“连续的， $r$ 个 $1$ ”(即形如 $11...1$，长度为 $r$ )。本题仅关注载荷部分：载荷按位发送，且不进行任何比特填充、字节对齐、$CRC$ 校验或转义。为了避免载荷误触发“伪旗标”，需要保证载荷内部不出现“连续的 $r$ 个 $1$ "

注意：帧的起止标志不计入载荷长度；不考虑跨帧拼接，也不考虑接收端的粘包现象。比特流按从高位到低位发送或从低位到高位发送均不影响计数结果。

​ 【引用结束】

给定整数 $n$ 和 $r$ 。一帧数据内容由一个长度恰为 $n$ 的二进制串构成(不含首尾标志)。标志定义为“连续 $r$ 个 $1$ "。统计有多少个长度为 $n$ 的二进制串，其任意连续的 $1$ 的长度严格小于(等价地，最大连续 $1$ 的长度至多为 $L=r-1$ )。

请将答案对 $10^9 +7$ 取模后输出。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≦T≦10^3)$ ，表示测试组数。

接下来 $T$ 行，每行输入两个整数 $n,r(1≦n≦10^3;1≦r≦10^9)$ 。

除此之外，保证单个测试文件的 $\sum n ≦10^3$ 。

输出描述

输出 $T$ 行，每行一个整数，表示长度为 $n$ 的二进制串中，最大连续 $1$ 的长度严格小于 $r$ 的方案数(对 $10^9 +7$ 取模)。

样例1

输入

3
5 3
7 10
8 2

输出

24
128
55