Dotcpp  >  编程题库  >  蓝桥杯2021年第十二届国赛真题-积木
题目 2617:

蓝桥杯2021年第十二届国赛真题-积木

时间限制: 3s 内存限制: 192MB 提交: 85 解决: 0

题目描述

小蓝有大量正方体的积木(所有积木完全相同),他准备用积木搭一个巨大的图形。
小蓝将积木全部平铺在地面上,而不垒起来,以便更稳定。他将积木摆成一行一行的,每行的左边对齐,形成最终的图形。最终图形一共 n 行。
第一行小蓝摆了 H1 = w 块积木。从第二行开始,第 i 行的积木数量 Hi 都至少比上一行多 L,至多比上一行多 R(当 L = 0 时表示可以和上一行的积木数量相同),即
Hii 1 + L ≤ Hi ≤ Hii 1 + R。
给定 x, y 和 z,请问满足以上条件的方案中,有多少种方案满足第 y 行的积木数量恰好为第 x 行的积木数量的 z 倍。

输入格式

输入一行包含 7 个整数 n,w, L, R, x, y,z,意义如上所述。

输出格式

输出一个整数, 表示满足条件的方案数,答案可能很大,请输出答案除以998244353 的余数。

样例输入

5 1 1 2 2 5 3

样例输出

4

提示

【样例说明】

符合条件的积木如图所示

【样例输入 2】
233 5 1 8 100 215 3
【样例输出 2】
308810105
【评测用例规模与约定】
对于 10% 的评测用例,1 ≤ n ≤ 10, 1 ≤ w ≤ 10, 0 ≤ L ≤ R ≤ 3;
对于 20% 的评测用例,1 ≤ n ≤ 20, 1 ≤ w ≤ 10, 0 ≤ L ≤ R ≤ 4;
对于 35% 的评测用例,1 ≤ n ≤ 500, 0 ≤ L ≤ R ≤ 10;
对于 50% 的评测用例,1 ≤ n ≤ 5000, 0 ≤ L ≤ R ≤ 10;
对于 60% 的评测用例,1 ≤ n ≤ 20000, 0 ≤ L ≤ R ≤ 10;
对于 70% 的评测用例,1 ≤ n ≤ 50000, 0 ≤ L ≤ R ≤ 10;
对于 85% 的评测用例,1 ≤ n ≤ 300000, 0 ≤ L ≤ R ≤ 10;
对于所有评测用例,1 ≤ n ≤ 500000, 1 ≤ w ≤ 109, 0 ≤ L ≤ R ≤ 40, 1 ≤ x < y ≤ n, 0 ≤ z ≤ 109

标签