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

大家好am是金奇人生话不多说讲题吧说明在一个图书馆整理活动中管理员需要将两种颜色的书籍红色和蓝色排列在书架上。规则如下1.蓝色书籍每次必须连续摆放恰好 k 本。2.红色书籍每次可以单独摆放也可以连续摆放任意数量。管理员需要计算书架长度在 [lr] 范围内的所有合法排列方案数结果对1097 取模。输入格式第一行包含两个整数 $t$ 和 $k$$1 \le t \le 1e51 \le k \le 1e5$表示测试用例数量和每组蓝色书籍的固定长度。接下来 t 行每行包含两个整数 l 和 r1≤l≤r≤1e6表示查询的区间。输出格式对于每个查询输出一个整数表示合法方案数模 $10^97$ 的结果。输入样例13 2 1 3 2 3 4 4输出样例16 5 5提示样例解释当 k2 时长度为 1 时只能是红色书籍1 种。长度为 2 时可能是 RR 或 BB2 种。长度为 3 时可能的组合有 RRR、RBB、BBR3 种总共有 1236 种。数据范围50% 数据 t≤100,1≤l≤r≤1e5100% 数据 t≤1000000,1≤l≤r≤1e6#includebits/stdc.h using namespace std; int t,k,f[1000005]; int qian[1000005]; int main() { cintk; f[0]1; for(int i1; i1000000; i){ f[i]f[i-1]; if(ik)f[i](f[i]f[i-k])%1000000007; } for(int i1; i1000000; i) qian[i](qian[i-1]f[i])%1000000007; int l,r; while(t--){ cinlr; cout(qian[r]-qian[l-1]1000000007)%1000000007endl; } return 0; }1. 状态定义与转移方程我们需要计算长度为 ii 的书架有多少种合法排列设数组f[i]表示这个数量。对于长度为 ii 的书架最后放置的书只有两种情况‌以红色书结尾‌红色书可以单独放也可以连续放。如果最后一位是红色那么前 i−1i−1 位只要是合法排列即可。因此这种情况贡献的方案数是f[i-1]。‌以蓝色书结尾‌题目规定蓝色书必须‌恰好连续摆放 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](当 ik)f[i]f[i−1](当 ik)‌边界条件‌f 1。这代表长度为 0 时有一种“空”的方案。这是为了处理当 ikik 时直接放置一组蓝色书的情况即f[k] f。2. 前缀和优化题目要求查询区间 [l,r][l,r] 内所有长度方案数的总和。如果每次查询都循环累加效率太低。我们可以预处理一个前缀和数组qianqian[i]∑j1if[j]qian[i]∑j1i​f[j]这样对于每次查询 [l,r][l,r]答案就是Answerqian[r]−qian[l−1]Answerqian[r]−qian[l−1]注意在模运算中减法可能导致负数所以需要写成(qian[r] - qian[l-1] MOD) % MOD。3. 代码实现#includebits/stdc.h using namespace std; int t,k,f; int qian; int main() { cintk; f[0]1; // 第一步动态规划计算每个长度的方案数 f[i] for(int i1; i1000000; i){ f[i]f[i-1]; // 情况1最后放一本红色书 if(ik) f[i](f[i]f[i-k])%1000000007; // 情况2最后放 k 本蓝色书 } // 第二步计算前缀和 qian[i] for(int i1; i1000000; i) qian[i](qian[i-1]f[i])%1000000007; int l,r; // 第三步处理查询 while(t--){ cinlr; // 利用前缀和差分计算区间和注意处理负数取模 cout(qian[r]-qian[l-1]1000000007)%1000000007endl; } return 0; }关键点总结‌f1的作用‌它是递推的基石。例如当 ikik 时f[k]会加上f这代表了“前0本书合法紧接着放k本蓝书”这一种情况。‌模运算处理‌在累加f[i]和计算前缀和时都要随时取模防止整数溢出。最后在输出结果时通过 1000000007确保减法结果为非负数。‌时间复杂度‌预处理部分为 O(N)O(N)每次查询为 O(1)O(1)总复杂度为 O(NT)O(NT)完全满足 N10,T10N10,T10 的数据范围要求。求关注来之不易......