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

 时间限制: 1s 内存限制: 128MB
题目描述

小蓝有大量正方体的积木（所有积木完全相同），他准备用积木搭一个巨大的图形。
小蓝将积木全部平铺在地面上，而不垒起来，以便更稳定。他将积木摆成一行一行的，每行的左边对齐，形成最终的图形。最终图形一共 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
提示

【样例说明】

符合条件的积木如图所示

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

【样例输入 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。


                
                
                

                                        

                        
                        

                                                            
                                
                                                        
                            
                            
                            
                        

                    

                

                


                

            

            

                

                    

                        
比赛公告

                    

                    

                        

                            
请基地所有同学们认真做题，以后会每两天发布一套蓝桥杯历年真题。
                        

                    

                

                

                    

                        
比赛状况