I think the [official editorial](https://codeforces.me/blog/entry/117606) of [problem G](https://codeforces.me/contest/1842/problem/G) is a little bit hard to understand for me, therefore I write a learning note, with an example, in English:↵
↵
Google Drive (Typo corrected): https://drive.google.com/file/d/1imUKYXcxQNw8wC28YFeTzEAkBV2wswMo/view?usp=sharing↵
↵
Tencent Docs (Typo corrected): https://docs.qq.com/pdf/DU1VaVUZHTUVrS0Nv2VOa09uYUJHYU9E↵
↵
The above pdf files do not contain code. My code:↵
↵
<spoiler summary="Spoiler">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define fastio cin.tie(0) -> sync_with_stdio(0) ↵
↵
//jiangly Codeforces↵
int P = 1e9+7;↵
using i64 = long long;↵
// assume -P <= x < 2P↵
int norm(int x) {↵
if (x < 0) {↵
x += P;↵
}↵
if (x >= P) {↵
x -= P;↵
}↵
return x;↵
}↵
template<class T>↵
T power(T a, i64 b) {↵
T res = 1;↵
for (; b; b /= 2, a *= a) {↵
if (b % 2) {↵
res *= a;↵
}↵
}↵
return res;↵
}↵
struct Z {↵
int x;↵
Z(int x = 0) : x(norm(x)) {}↵
Z(i64 x) : x(norm((int)(x % P))) {}↵
int val() const {↵
return x;↵
}↵
Z operator-() const {↵
return Z(norm(P - x));↵
}↵
Z inv() const {↵
assert(x != 0);↵
return power(*this, P - 2);↵
}↵
Z &operator*=(const Z &rhs) {↵
x = i64(x) * rhs.x % P;↵
return *this;↵
}↵
Z &operator+=(const Z &rhs) {↵
x = norm(x + rhs.x);↵
return *this;↵
}↵
Z &operator-=(const Z &rhs) {↵
x = norm(x - rhs.x);↵
return *this;↵
}↵
Z &operator/=(const Z &rhs) {↵
return *this *= rhs.inv();↵
}↵
friend Z operator*(const Z &lhs, const Z &rhs) {↵
Z res = lhs;↵
res *= rhs;↵
return res;↵
}↵
friend Z operator+(const Z &lhs, const Z &rhs) {↵
Z res = lhs;↵
res += rhs;↵
return res;↵
}↵
friend Z operator-(const Z &lhs, const Z &rhs) {↵
Z res = lhs;↵
res -= rhs;↵
return res;↵
}↵
friend Z operator/(const Z &lhs, const Z &rhs) {↵
Z res = lhs;↵
res /= rhs;↵
return res;↵
}↵
friend std::istream &operator>>(std::istream &is, Z &a) {↵
i64 v;↵
is >> v;↵
a = Z(v);↵
return is;↵
}↵
friend std::ostream &operator<<(std::ostream &os, const Z &a) {↵
return os << a.val();↵
}↵
};↵
↵
#define DEBUG 0↵
↵
void debug(const char* p){↵
#if DEBUG↵
freopen(p, "r", stdin); ↵
#else↵
fastio;↵
#endif ↵
}↵
↵
int main(void){↵
debug("test1.txt");↵
int n, m, v;↵
cin >> n >> m >> v;↵
Z zv = Z(v);↵
vector<Z> a(n+1);↵
for(int i = 1; i <= n; ++i) cin >> a[i];↵
vector<vector<Z>> dp(n+1, vector<Z>(min(n, m)+1));↵
dp[0][0] = 1;↵
Z invn = Z(n).inv(), ans = 0;↵
for(int r = 0; r < n; ++r){↵
for(int s = 0; s <= r && s <= m; ++s){↵
dp[r+1][s] += (a[r+1] + zv * s) * dp[r][s];↵
if(s < m) dp[r+1][s+1] += Z(r+1) * invn * zv * Z(m - s) * dp[r][s];↵
}↵
}↵
for(int s = 0; s <= min(n, m); ++s) ans += dp[n][s];↵
cout << ans << "\n";↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
and my submission: [submission:211097938].↵
↵
Be careful when handling indices! Here is a wrong submission with Runtime Error: [submission:211089726].
↵
Google Drive (Typo corrected): https://drive.google.com/file/d/1imUKYXcxQNw8wC28YFeTzEAkBV2wswMo/view?usp=sharing↵
↵
Tencent Docs (Typo corrected): https://docs.qq.com/pdf/DU
↵
The above pdf files do not contain code. My code:↵
↵
<spoiler summary="Spoiler">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define fastio cin.tie(0) -> sync_with_stdio(0) ↵
↵
//jiangly Codeforces↵
int P = 1e9+7;↵
using i64 = long long;↵
// assume -P <= x < 2P↵
int norm(int x) {↵
if (x < 0) {↵
x += P;↵
}↵
if (x >= P) {↵
x -= P;↵
}↵
return x;↵
}↵
template<class T>↵
T power(T a, i64 b) {↵
T res = 1;↵
for (; b; b /= 2, a *= a) {↵
if (b % 2) {↵
res *= a;↵
}↵
}↵
return res;↵
}↵
struct Z {↵
int x;↵
Z(int x = 0) : x(norm(x)) {}↵
Z(i64 x) : x(norm((int)(x % P))) {}↵
int val() const {↵
return x;↵
}↵
Z operator-() const {↵
return Z(norm(P - x));↵
}↵
Z inv() const {↵
assert(x != 0);↵
return power(*this, P - 2);↵
}↵
Z &operator*=(const Z &rhs) {↵
x = i64(x) * rhs.x % P;↵
return *this;↵
}↵
Z &operator+=(const Z &rhs) {↵
x = norm(x + rhs.x);↵
return *this;↵
}↵
Z &operator-=(const Z &rhs) {↵
x = norm(x - rhs.x);↵
return *this;↵
}↵
Z &operator/=(const Z &rhs) {↵
return *this *= rhs.inv();↵
}↵
friend Z operator*(const Z &lhs, const Z &rhs) {↵
Z res = lhs;↵
res *= rhs;↵
return res;↵
}↵
friend Z operator+(const Z &lhs, const Z &rhs) {↵
Z res = lhs;↵
res += rhs;↵
return res;↵
}↵
friend Z operator-(const Z &lhs, const Z &rhs) {↵
Z res = lhs;↵
res -= rhs;↵
return res;↵
}↵
friend Z operator/(const Z &lhs, const Z &rhs) {↵
Z res = lhs;↵
res /= rhs;↵
return res;↵
}↵
friend std::istream &operator>>(std::istream &is, Z &a) {↵
i64 v;↵
is >> v;↵
a = Z(v);↵
return is;↵
}↵
friend std::ostream &operator<<(std::ostream &os, const Z &a) {↵
return os << a.val();↵
}↵
};↵
↵
#define DEBUG 0↵
↵
void debug(const char* p){↵
#if DEBUG↵
freopen(p, "r", stdin); ↵
#else↵
fastio;↵
#endif ↵
}↵
↵
int main(void){↵
debug("test1.txt");↵
int n, m, v;↵
cin >> n >> m >> v;↵
Z zv = Z(v);↵
vector<Z> a(n+1);↵
for(int i = 1; i <= n; ++i) cin >> a[i];↵
vector<vector<Z>> dp(n+1, vector<Z>(min(n, m)+1));↵
dp[0][0] = 1;↵
Z invn = Z(n).inv(), ans = 0;↵
for(int r = 0; r < n; ++r){↵
for(int s = 0; s <= r && s <= m; ++s){↵
dp[r+1][s] += (a[r+1] + zv * s) * dp[r][s];↵
if(s < m) dp[r+1][s+1] += Z(r+1) * invn * zv * Z(m - s) * dp[r][s];↵
}↵
}↵
for(int s = 0; s <= min(n, m); ++s) ans += dp[n][s];↵
cout << ans << "\n";↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
and my submission: [submission:211097938].↵
↵
Be careful when handling indices! Here is a wrong submission with Runtime Error: [submission:211089726].
