C++（作問者解答）
#include <bits/stdc++.h>
using namespace std;
#define N 500010
#define ll long long
#define MOD (ll)998244353
#define rep(i, n) for(ll i = 0; i < n; ++i)
#define eb emplace_back
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define vi vector<int>
#define pii pair<int,int>
#define pll pair<ll,ll>
ll k[N];
ll r[N];
ll r2[N];
bool b[30];
int main(void) {
ll n, m;
ll ans, s, p;
ll a, x;
x = MOD - 2;
rep(i, 30) {
if (x % 2 == 1)b[i] = true;
else b[i] = false;
x /= 2;
}
k[0] = (ll)1;
r[0] = (ll)1;
rep(i, N - 1) {
k[i + 1] = (k[i] * (i + 1)) % MOD;
r[i + 1] = (ll)1;
x = k[i + 1];
rep(j, 30) {
if (b[j]) {
r[i + 1] = (r[i + 1] * x) % MOD;
}
x = (x*x) % MOD;
}
}
r2[0] = 1;
r2[1] = (MOD + 1) / 2;
rep(i, N - 2)r2[i + 2] = (r2[i + 1] * r2[1]) % MOD;
cin >> n >> m;
m++;
ans = 0;
p = 1;
s = 0;
rep(i, n) {
cin >> a;
m--;
if (m <= s) {
x = (r[m] * r[s - m]) % MOD;
x = (x*k[s]) % MOD;
x = (x*r2[s]) % MOD;
p = (p + MOD - x) % MOD;
}
//cout << s << " " << m << " " << p << endl;
rep(j, a) {
s++;
if (m <= s) {
x = (r[m - 1] * r[s - m]) % MOD;
x = (x*k[s - 1]) % MOD;
x = (x*r2[s]) % MOD;
p = (p + MOD - x) % MOD;
}
//cout << s << " " << m << " " << p << endl;
}
ans = (ans + p) % MOD;
//cout << ans << endl;
}
cout << ans << endl;
return 0;
}
Java
import java.util.*;
import java.util.function.BiFunction;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int[] A = new int[N];
for (int i = 0; i < N; i++) {
A[i] = sc.nextInt();
}
long mod = 998244353;
int ma = 5 * (int)Math.pow(10, 5) + 1;
long[] fac = new long[ma];
fac[0] = 1;
long[] invFac = new long[ma];
invFac[0] = 1;
for (int i = 1; i < ma; i++) {
fac[i] = fac[i - 1] * i % mod;
invFac[i] = invFac[i - 1] * modPow(i, mod - 2, mod) % mod;
}
long[] inv2Ai = new long[ma];
inv2Ai[0] = 1;
inv2Ai[1] = (mod + 1) / 2;
for (int i = 0; i < ma - 2; i++) {
inv2Ai[i + 2] = (inv2Ai[i + 1] * inv2Ai[1]) % mod;
}
BiFunction<Integer, Integer, Long> nCr = (n, r) -> {
long x = fac[n];
x *= invFac[r] * invFac[n - r] % mod;
return x % mod;
};
long p = 1;
int s = 0;
int m = M;
long ans = 0;
for (int i = 0; i < N; i++) {
long a = A[i];
if (m <= s) {
long x = (nCr.apply(s, m) * inv2Ai[s]) % mod;
p = (p + mod - x) % mod;
}
for (int j = 0; j < a; j++) {
s += 1;
if (m <= s) {
long x = (nCr.apply(s - 1, m - 1) * inv2Ai[s]) % mod;
p = (p + mod - x) % mod;
}
}
ans = (ans + p) % mod;
m -= 1;
}
System.out.println(ans);
}
static long modPow(long x, long p, long mod) {
long ret = 1;
while (0 < p) {
if ((p & 1) == 1) {
ret = ret * x % mod;
}
x = x * x % mod;
p >>= 1;
}
return ret;
}
}
Python
(実行環境をPyPyにして提出する必要があります)
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
mod = 998244353
ma = 5 * 10**5 + 1
fac = [0] * ma
fac[0] = 1
inv_fac = [0] * ma
inv_fac[0] = 1
for i in range(1, ma):
fac[i] = fac[i - 1] * i % mod
inv_fac[i] = inv_fac[i - 1] * pow(i, -1, mod) % mod
inv_2_ai = [0] * ma
inv_2_ai[0] = 1
inv_2_ai[1] = (mod + 1) // 2
for i in range(ma - 2):
inv_2_ai[i + 2] = (inv_2_ai[i + 1] * inv_2_ai[1]) % mod
# same as: inv_2_ai = [pow(pow(2, i, mod), mod - 2, mod) for i in range(ma + 1)]
def nCr(n, r):
# n! / (r!(n-r)!)
x = fac[n]
x *= inv_fac[r] * inv_fac[n - r] % mod
return x % mod
p = 1
s = 0
m = M
ans = 0
for i in range(N):
a = A[i]
if m <= s:
x = (nCr(s, m) * inv_2_ai[s]) % mod
p = (p + mod - x) % mod
for j in range(a):
s += 1
if m <= s:
x = (nCr(s - 1, m - 1) * inv_2_ai[s]) % mod
p = (p + mod - x) % mod
ans = (ans + p) % mod
m -= 1
print(ans)
