E. 喝饮料 -- math,dp

 1 

#include 
 2 using std::cin;
 3 using std::cout;
 4 using i64 = long long;
 5 constexpr int N = 1e3 + 5;
 6 constexpr int P = 998244353;
 7 __int128 dp[N][N];
 8 __int128 prefix[N][N];
 9 int a[N];
10 template
11 inline void read(T& n) {
12     T x = 0, f = 1;
13     char ch = getchar();
14     while (!isdigit(ch)) { if (ch == '-') f = -f;ch = getchar();}
15     while (isdigit(ch)) {x = x * 10 + (ch - '0');ch = getchar();}
16     n = x * f;
17     return;
18 }
19 
20 template<class T>
21 inline void write(T x) {
22     if (x < 0) x = -x, putchar('-');
23     if (x > 9) write(x / 10);
24     putchar('0' + x % 10);
25 }
26 int main(){
27     std::ios::sync_with_stdio(false);
28     std::cin.tie(nullptr);
29 
30     int n,k;
31     cin >> n >> k;
32     for(int i = 1; i <= n ; i++){
33         cin >> a[i];
34     }
35     for(int i = 1 ; i <= k + 1; i++){
36         prefix[0][i] = 1;
37     }
38     for(int i = 1; i <= n; i++){
39         for(int j = 1; j <= k+1; j++){
40             dp[i][j] = (dp[i][j] +
41              prefix[i-1][j] - prefix[i - 1][std::max(0,j-a[i]-1)]) % P;
42             //std::cerr << "dp" <<"[" << i  << "]" << "[" << j << "] = " << dp[i][j] << "\n"; 
43         }
44         for(int j = 1; j <= 1+k; j++){
45             prefix[i][j] = prefix[i][j-1] + dp[i][j];
46         }
47     }
48     /*
49         dp[1][5] = dp[0][0] + dp[0][1] + dp[0][2] + ...
50 
51     */
52     __int128 ans = dp[n][k + 1] % P;
53     write(ans);
54     return 0;
55 }