#P5264. 空洞

    ID: 4302 传统题 1000ms 233MiB 尝试: 3 已通过: 3 难度: 7 上传者: 标签>CF2200提高容斥原理0/1 背包倒序更新避免重复使用快速幂模逆元

空洞

题目描述

给定一个 nn 维超矩形 ∏i=1n[0,ri]\prod_{i=1}^{n}[0,r_i]。将其中所有满足 ∑i=1nxi≤s\sum_{i=1}^n x_i\le s 的点填满液体,求液体的体积。以边长为 11 的 nn 维超立方体的体积为单位。

输入格式

第一行两个整数 n,sn,s。第二行 nn 个整数 r1,…,rnr_1,\ldots,r_n,表示各维的长度。

输出格式

输出一行一个整数,表示体积对 998244353998244353 取模的结果。若体积为分数 ab\frac ab,输出 a×b−1 mod 998244353a\times b^{-1}\bmod 998244353。

样例 1

2 2
1 4
499122178

液体体积为 32\frac32,其模值为 499122178499122178。

样例 2

3 10
3 4 5
665496294

数据范围

  • 10%10\% 的数据满足 n=2n=2。
  • 50%50\% 的数据满足 n≤20n\le20。
  • 另外 10%10\% 的数据满足对所有 ii 都有 ri=sr_i=s。
  • 所有数据满足 1≤n≤5001\le n\le500,s≤109s\le10^9,1≤ri≤5001\le r_i\le500。

原 PDF 题面第 1 页 · 原 PDF 题面第 2 页