书架排列问题(区间查询)

大家好，am是金奇人生，话不多说，讲题吧！

说明

在一个图书馆整理活动中，管理员需要将两种颜色的书籍（红色和蓝色）排列在书架上。规则如下：

1.蓝色书籍每次必须连续摆放恰好 k 本。

2.红色书籍每次可以单独摆放，也可以连续摆放任意数量。

管理员需要计算书架长度在 [l，r] 范围内的所有合法排列方案数，结果对109+7 取模。

输入格式

第一行包含两个整数 $t$ 和 $k$（$1 \le t \le 1e5，1 \le k \le 1e5$），表示测试用例数量和每组蓝色书籍的固定长度。

接下来 t 行，每行包含两个整数 l 和 r（1≤l≤r≤1e6），表示查询的区间。

输出格式

对于每个查询，输出一个整数，表示合法方案数模 $10^9+7$ 的结果。

输入样例1

3 2 1 3 2 3 4 4

输出样例1

6 5 5

提示

样例解释

当 k=2 时：

长度为 1 时，只能是红色书籍（1 种）。

长度为 2 时，可能是 RR 或 BB（2 种）。

长度为 3 时，可能的组合有 RRR、RBB、BBR（3 种），总共有 1+2+3=6 种。

数据范围

50% 数据 t≤100,1≤l≤r≤1e5

100% 数据 t≤1000000,1≤l≤r≤1e6

#include<bits/stdc++.h> using namespace std; int t,k,f[1000005]; int qian[1000005]; int main() { cin>>t>>k; f[0]=1; for(int i=1; i<=1000000; i++){ f[i]+=f[i-1]; if(i>=k)f[i]=(f[i]+f[i-k])%1000000007; } for(int i=1; i<=1000000; i++) qian[i]=(qian[i-1]+f[i])%1000000007; int l,r; while(t--){ cin>>l>>r; cout<<(qian[r]-qian[l-1]+1000000007)%1000000007<<endl; } return 0; }

1. 状态定义与转移方程

我们需要计算长度为 ii 的书架有多少种合法排列，设数组f[i]表示这个数量。

对于长度为 ii 的书架，最后放置的书只有两种情况：

1. ‌以红色书结尾‌：红色书可以单独放，也可以连续放。如果最后一位是红色，那么前 i−1i−1 位只要是合法排列即可。因此，这种情况贡献的方案数是f[i-1]。
2. ‌以蓝色书结尾‌：题目规定蓝色书必须‌恰好连续摆放 kk 本‌。这意味着如果书架以蓝色结尾，那么最后 kk 个位置必须全部是蓝色，且这 kk 本蓝色书作为一个整体，其前面的 i−ki−k 个位置必须是合法排列。因此，这种情况贡献的方案数是f[i-k]（前提是 i≥ki≥k）。

综合起来，状态转移方程为：
f[i]=f[i−1]+f[i−k](当 i≥k)f[i]=f[i−1]+f[i−k](当 i≥k)
f[i]=f[i−1](当 i<k)f[i]=f[i−1](当 i<k)

‌边界条件‌：f = 1。这代表长度为 0 时有一种“空”的方案。这是为了处理当 i=ki=k 时，直接放置一组蓝色书的情况（即f[k] += f）。

2. 前缀和优化

题目要求查询区间 [l,r][l,r] 内所有长度方案数的总和。如果每次查询都循环累加，效率太低。我们可以预处理一个前缀和数组qian：
qian[i]=∑j=1if[j]qian[i]=∑j=1i​f[j]

这样，对于每次查询 [l,r][l,r]，答案就是：
Answer=qian[r]−qian[l−1]Answer=qian[r]−qian[l−1]

注意：在模运算中，减法可能导致负数，所以需要写成(qian[r] - qian[l-1] + MOD) % MOD。

3. 代码实现：

#include<bits/stdc++.h> using namespace std; int t,k,f; int qian; int main() { cin>>t>>k; f[0]=1; // 第一步：动态规划计算每个长度的方案数 f[i] for(int i=1; i<=1000000; i++){ f[i]+=f[i-1]; // 情况1：最后放一本红色书 if(i>=k) f[i]=(f[i]+f[i-k])%1000000007; // 情况2：最后放 k 本蓝色书 } // 第二步：计算前缀和 qian[i] for(int i=1; i<=1000000; i++) qian[i]=(qian[i-1]+f[i])%1000000007; int l,r; // 第三步：处理查询 while(t--){ cin>>l>>r; // 利用前缀和差分计算区间和，注意处理负数取模 cout<<(qian[r]-qian[l-1]+1000000007)%1000000007<<endl; } return 0; }

关键点总结

1. ‌f=1的作用‌：它是递推的基石。例如当 i=ki=k 时，f[k]会加上f，这代表了“前0本书合法，紧接着放k本蓝书”这一种情况。
2. ‌模运算处理‌：在累加f[i]和计算前缀和时都要随时取模，防止整数溢出。最后在输出结果时，通过+ 1000000007确保减法结果为非负数。
3. ‌时间复杂度‌：预处理部分为 O(N)O(N)，每次查询为 O(1)O(1)，总复杂度为 O(N+T)O(N+T)，完全满足 N=10,T=10N=10,T=10 的数据范围要求。

求关注，来之不易......