Submission #65320388

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define fre(x) freopen(#x".in", "r", stdin); freopen(#x".out", "w", stdout)
#define ck(x)  { cout << "check " << x << endl;}
#define int long long
#define double long double
#define inf 0x3fffffffffffffff

template<class T>
constexpr T power(T a, int b) {
    T res = 1;
    for (; b; b /= 2, a *= a)
        if (b % 2) res *= a;
    return res;
}
constexpr int mul(int a, int b, int p) {
    int res = a * b % p;
    if (res < 0) res += p;
    return res;
}
template<int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(int x) : x{norm(x % getMod())} {}
    static int Mod;
    constexpr static int getMod() { return P > 0 ? P : Mod;}
    constexpr static void setMod(int Mod_) { Mod = Mod_;}
    constexpr int norm(int x) const { if (x < 0) x += getMod(); if (x >= getMod()) x -= getMod(); return x;}
    constexpr int val() const { return x;}
    explicit constexpr operator int() const { return x;}
    constexpr MInt operator-() const { MInt res; res.x = norm(getMod() - x); return res;}
    constexpr MInt inv() const { assert(x != 0); return power(*this, getMod() - 2);}
    constexpr MInt &operator*=(MInt rhs) & { x = mul(x, rhs.x, getMod()); return *this;}
    constexpr MInt &operator+=(MInt rhs) & { x = norm(x + rhs.x); return *this;}
    constexpr MInt &operator-=(MInt rhs) & { x = norm(x - rhs.x); return *this;}
    constexpr MInt &operator/=(MInt rhs) & { return *this *= rhs.inv();}
    friend constexpr MInt operator*(MInt lhs, MInt rhs) { MInt res = lhs; res *= rhs; return res;}
    friend constexpr MInt operator+(MInt lhs, MInt rhs) { MInt res = lhs; res += rhs; return res;}
    friend constexpr MInt operator-(MInt lhs, MInt rhs) { MInt res = lhs; res -= rhs; return res;}
    friend constexpr MInt operator/(MInt lhs, MInt rhs) { MInt res = lhs; res /= rhs; return res;}
    friend constexpr istream &operator>>(istream &is, MInt &a) { int v; is >> v; a = MInt(v); return is;}
    friend constexpr ostream &operator<<(ostream &os, const MInt &a) { return os << a.val();}
    friend constexpr bool operator==(MInt lhs, MInt rhs) { return lhs.val() == rhs.val();}
    friend constexpr bool operator!=(MInt lhs, MInt rhs) { return lhs.val() != rhs.val();}
};

template<>
int MInt<0>::Mod = 998244353;

template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

constexpr int modp = 998244353;
using Z = MInt<modp>;

// template<int P>
// int MInt<P>::Mod = P;

// using Z = MInt<0>;
// Z::setMod(mod);

Z qpow(Z k, int n) {
	Z s = 1;
	for ( ; n; n >>= 1, k = k * k) 
		if(n & 1) s = s * k;
	return s;
}

struct math {
	int size = 0;
	vector<Z> fac, inv;
	math(int n = 0) {
		init(n);
	}
	void init(int n) {
		fac.resize(n + 2);
		inv.resize(n + 2);
		fac[0] = 1;
		for (int i = size + 1; i <= n; i++) {
			fac[i] = fac[i - 1] * i;
		}
		inv[n] = qpow(fac[n], modp - 2);
		for (int i = n; i >= size + 1; i--) {
			inv[i - 1] = inv[i] * i;
		}
		size = n;
	}
	Z C(int n, int m) {
		if (n < m || m < 0) return 0;
		if(n > size) init(n);
		return fac[n] * inv[m] * inv[n - m];
	}
} binom;

Z C(int n, int m) {
	return binom.C(n, m); 
}
Z C(Z n, Z m) {
	return binom.C(n.val(), m.val()); 
}
Z fac(int n) {
	if (binom.size < n) binom.init(n);
	return binom.fac[n];
}
Z bfC(int n, int m) {
	if (n < m || m < 0) return 0;
	Z s = 1;
	for (int i = n - m + 1; i <= n; i++) {
		s *= i;
	}
	return s / fac(m);
}


//-------------- templates above --------------


void solve() {
	int n, k;
	cin >> n >> k;
	vector<Z> a(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		a[i] += a[i - 1];
	}
	vector s(n + 1, vector<Z>(k + 1));
	for (int i = 0; i <= n; i++) {
		s[i][0] = 1;
		for (int j = 1; j <= k; j++) {
			s[i][j] = s[i][j - 1] * a[i];
		}
	}
	auto ss = s;
	for (int i = 0; i <= k; i++) {
		for (int j = 1; j <= n; j++) {
			ss[j][i] += ss[j - 1][i];
		}
	}
	Z ans = 0;
	for (int i = 0; i <= k; i++) {
		Z res = 0;
		for (int r = 1; r <= n; r++) {
			res += s[r][i] * ss[r - 1][k - i];
		}
		ans += ((k - i) & 1 ? -1 : 1) * C(k, i) * res;
	}
	cout << ans << "\n";
}


signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int T = 1;
	while (T--) {
		solve();
	}
	return 0;
}

Submission Info

Judge Result