2617 問題 Q: 藍橋杯2021年第十二屆國賽真題-積木
時間限制: 1s
內(nèi)存限制: 128MB 提交: 89 解決: 0
題目描述
小藍有大量正方體的積木（所有積木完全相同），他準(zhǔn)備用積木搭一個巨大的圖形。
小藍將積木全部平鋪在地面上，而不壘起來，以便更穩(wěn)定。他將積木擺成一行一行的，每行的左邊對齊，形成最終的圖形。最終圖形一共 n 行。
第一行小藍擺了 H1 = w 塊積木。從第二行開始，第 i 行的積木數(shù)量 Hi 都至少比上一行多 L，至多比上一行多 R（當(dāng) L = 0 時表示可以和上一行的積木數(shù)量相同），即
Hii 1 + L ≤ Hi ≤ Hii 1 + R。
給定 x, y 和 z，請問滿足以上條件的方案中，有多少種方案滿足第 y 行的積木數(shù)量恰好為第 x 行的積木數(shù)量的 z 倍。
小藍將積木全部平鋪在地面上，而不壘起來，以便更穩(wěn)定。他將積木擺成一行一行的，每行的左邊對齊，形成最終的圖形。最終圖形一共 n 行。
第一行小藍擺了 H1 = w 塊積木。從第二行開始，第 i 行的積木數(shù)量 Hi 都至少比上一行多 L，至多比上一行多 R（當(dāng) L = 0 時表示可以和上一行的積木數(shù)量相同），即
Hii 1 + L ≤ Hi ≤ Hii 1 + R。
給定 x, y 和 z，請問滿足以上條件的方案中，有多少種方案滿足第 y 行的積木數(shù)量恰好為第 x 行的積木數(shù)量的 z 倍。
輸入
輸入一行包含 7 個整數(shù) n,w, L, R, x, y,z，意義如上所述。
輸出
輸出一個整數(shù), 表示滿足條件的方案數(shù)，答案可能很大，請輸出答案除以998244353 的余數(shù)。
樣例輸入
5 1 1 2 2 5 3
樣例輸出
4
提示
【樣例說明】
符合條件的積木如圖所示
【樣例輸入 2】
233 5 1 8 100 215 3
【樣例輸出 2】
308810105
【評測用例規(guī)模與約定】
對于 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。
比賽公告
——————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————