[Learning Notes]On CodeTON5 Problem G Tenzing and Random Operations
Difference between en7 and en8, changed 37 character(s)
I think the [official editorial](https://codeforces.net/blog/entry/117606) of [problem G](https://codeforces.net/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].

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English dfsof 2023-06-28 05:20:51 37
en7 English dfsof 2023-06-28 05:18:30 73
en6 English dfsof 2023-06-26 08:55:00 58
en5 English dfsof 2023-06-26 08:52:13 73
en4 English dfsof 2023-06-26 08:26:20 0 (published)
en3 English dfsof 2023-06-26 08:26:04 22
en2 English dfsof 2023-06-26 08:25:19 5
en1 English dfsof 2023-06-26 08:25:03 3418 Initial revision (saved to drafts)