2617 問(wèn)題 E: 藍(lán)橋杯2021年第十二屆國(guó)賽真題-積木
時(shí)間限制: 1s
內(nèi)存限制: 128MB 提交: 89 解決: 0
題目描述
小藍(lán)有大量正方體的積木（所有積木完全相同），他準(zhǔn)備用積木搭一個(gè)巨大的圖形。
小藍(lán)將積木全部平鋪在地面上，而不壘起來(lái)，以便更穩(wěn)定。他將積木擺成一行一行的，每行的左邊對(duì)齊，形成最終的圖形。最終圖形一共 n 行。
第一行小藍(lán)擺了 H1 = w 塊積木。從第二行開(kāi)始，第 i 行的積木數(shù)量 Hi 都至少比上一行多 L，至多比上一行多 R（當(dāng) L = 0 時(shí)表示可以和上一行的積木數(shù)量相同），即
Hii 1 + L ≤ Hi ≤ Hii 1 + R。
給定 x, y 和 z，請(qǐng)問(wèn)滿(mǎn)足以上條件的方案中，有多少種方案滿(mǎn)足第 y 行的積木數(shù)量恰好為第 x 行的積木數(shù)量的 z 倍。
小藍(lán)將積木全部平鋪在地面上，而不壘起來(lái)，以便更穩(wěn)定。他將積木擺成一行一行的，每行的左邊對(duì)齊，形成最終的圖形。最終圖形一共 n 行。
第一行小藍(lán)擺了 H1 = w 塊積木。從第二行開(kāi)始，第 i 行的積木數(shù)量 Hi 都至少比上一行多 L，至多比上一行多 R（當(dāng) L = 0 時(shí)表示可以和上一行的積木數(shù)量相同），即
Hii 1 + L ≤ Hi ≤ Hii 1 + R。
給定 x, y 和 z，請(qǐng)問(wèn)滿(mǎn)足以上條件的方案中，有多少種方案滿(mǎn)足第 y 行的積木數(shù)量恰好為第 x 行的積木數(shù)量的 z 倍。
輸入
輸入一行包含 7 個(gè)整數(shù) n,w, L, R, x, y,z，意義如上所述。
輸出
輸出一個(gè)整數(shù), 表示滿(mǎn)足條件的方案數(shù)，答案可能很大，請(qǐng)輸出答案除以998244353 的余數(shù)。
樣例輸入
5 1 1 2 2 5 3
樣例輸出
4
提示
【樣例說(shuō)明】
符合條件的積木如圖所示
【樣例輸入 2】
233 5 1 8 100 215 3
【樣例輸出 2】
308810105
【評(píng)測(cè)用例規(guī)模與約定】
對(duì)于 10% 的評(píng)測(cè)用例，1 ≤ n ≤ 10, 1 ≤ w ≤ 10, 0 ≤ L ≤ R ≤ 3；
對(duì)于 20% 的評(píng)測(cè)用例，1 ≤ n ≤ 20, 1 ≤ w ≤ 10, 0 ≤ L ≤ R ≤ 4；
對(duì)于 35% 的評(píng)測(cè)用例，1 ≤ n ≤ 500, 0 ≤ L ≤ R ≤ 10；
對(duì)于 50% 的評(píng)測(cè)用例，1 ≤ n ≤ 5000, 0 ≤ L ≤ R ≤ 10；
對(duì)于 60% 的評(píng)測(cè)用例，1 ≤ n ≤ 20000, 0 ≤ L ≤ R ≤ 10；
對(duì)于 70% 的評(píng)測(cè)用例，1 ≤ n ≤ 50000, 0 ≤ L ≤ R ≤ 10；
對(duì)于 85% 的評(píng)測(cè)用例，1 ≤ n ≤ 300000, 0 ≤ L ≤ R ≤ 10；
對(duì)于所有評(píng)測(cè)用例，1 ≤ n ≤ 500000, 1 ≤ w ≤ 109, 0 ≤ L ≤ R ≤ 40, 1 ≤ x < y ≤ n, 0 ≤ z ≤ 109。
比賽公告
請(qǐng)對(duì)本次比賽進(jìn)行一些描述，公告內(nèi)容應(yīng)當(dāng)包含：
比賽的創(chuàng)辦者或組織；
本次比賽的目的或意義；
本次比賽的考點(diǎn)、語(yǔ)言或