# Sol BN03

## A. Lợi và lợn

### Sub 2:
$f[i][j][u]$ là số cách đi mà thằng bên trái đang ở ($i, j$) và thằng bên phải đang ở hàng $u$ (vì từ $3$ biến này có thể suy ra cột của thằng bên phải).

#include <bits/stdc++.h>
#define VanLoi ""
#define gb(i, j) ((i >> j) & 1)
 
using namespace std;
 
const int N = (int)500 + 5, MOD = (int)1e9 + 7, mod = (int)1e9 + 20041203;
 
int n, m, f[205][205][205];
char a[N][N];
 
void add(int& x, int y) {
    x += y;
    if (x >= MOD) x -= MOD;
}
 
int ci[2] = { 0, 1 };
int di[2] = { 1, 0 };
 
bool inside(int i, int j) {
    if (1 <= i && i <= n && 1 <= j && j <= m) return true;
    return false;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen(VanLoi".inp", "r", stdin);
    freopen(VanLoi".out", "w", stdout);
#endif
    cin >> n >> m;
    int res = 0;
    int diagonal = n + m - 1;
    int pos = (diagonal - 1) / 2 + 2;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) cin >> a[i][j];
    if (a[1][1] == a[n][m]) f[1][1][n] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            for (int u = 1; u <= n; u++) {
                int v = n + m + 2 - i - j - u;
                if (v < 1 || v > m) continue;
                if (f[i][j][u] == 0) continue;
                for (int t = 0; t <= 1; t++) {
                    int new_i = i + ci[t];
                    int new_j = j + di[t];
                    if (!inside(new_i, new_j)) continue;
                    for (int tt = 0; tt <= 1; tt++) {
                        int new_u = u - ci[tt];
                        int new_v = v - di[tt];
                        if (!inside(new_u, new_v)) continue;
                        if (a[new_i][new_j] == a[new_u][new_v]) add(f[new_i][new_j][new_u], f[i][j][u]);
                    }
                }
            }
        }
    if (diagonal & 1) {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) if (i + j == pos) add(res, f[i][j][i]);
    }
    else {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) if (i + j == pos) {
                for (int t = 0; t <= 1; t++) {
                    int new_i = i + ci[t];
                    int new_j = j + di[t];
                    if (inside(new_i, new_j) && a[i][j] == a[new_i][new_j]) {
                        add(res, f[i][j][new_i]);
                    }
                }
            }
    }
    cout << res;
}

### Sub 3:

Xử lí theo từng đường chéo từ ngoài vào trong hoặc từ trong ra ngoài.

#include <bits/stdc++.h>
#define VanLoi ""
#define gb(i, j) ((i >> j) & 1)
 
using namespace std;
 
const int N = (int)500 + 5, MOD = (int)1e9 + 7, mod = (int)1e9 + 20041203;
 
int n, m, f[N][N], g[N][N], res;
char a[N][N];
 
vector <int> list_i[N * 2];
 
void add(int& x, int y) {
    x += y;
    if (x >= MOD) x -= MOD;
}
 
int ci[2] = { 0, 1 };
int di[2] = { 1, 0 };
 
bool inside(int i, int j) {
    if (1 <= i && i <= n && 1 <= j && j <= m) return true;
    return false;
}
 
void process(int i, int j, int u, int v) {
    for (int le = 0; le <= 1; le++) {
        int new_i = i + ci[le];
        int new_j = j + di[le];
        if (inside(new_i, new_j)) {
            for (int ri = 0; ri <= 1; ri++) {
                int new_u = u - ci[ri];
                int new_v = v - di[ri];
                if (inside(new_u, new_v) && a[new_i][new_j] == a[new_u][new_v]) {
                    add(g[new_i][new_u], f[i][u]);
                }
            }
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    int diagonal = n + m - 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            list_i[i + j].push_back(i);
        }
    if (a[1][1] != a[n][m]) {
        cout << 0;
        exit(0);
    }
    f[1][n] = 1;
    for (int posle = 2, x = (diagonal - 1) / 2 + 1; posle <= x; posle++) {
        for (auto i : list_i[posle]) {
            int posri = n + m + 2 - posle;
            for (auto u : list_i[posri]) {
                if (f[i][u] == 0) continue;
                process(i, posle - i, u, posri - u);
            }
        }
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) f[i][j] = g[i][j], g[i][j] = 0;
    }
    if (diagonal & 1) {
        for (int i = 1; i <= n; i++) add(res, f[i][i]);
    }
    else {
        for (int i = 1; i <= n; i++) add(res, f[i][i]), add(res, f[i][i + 1]);
    }
    cout << res;
}

### Code Hoa

#include <bits/stdc++.h>
#define name "cownav"
#define fi(i,a,b) for(int i = a; i <= b; i++)
#define fid(i,a,b) for(int i = a; i >= b; i--)
#define ll long long
#define f first
#define se second
#define pii pair<int, ll>
#define getbit(i, j) ((i >> j) & 1)
#define pb push_back
#define all(v) v.begin(), v.end()
#define maxn 505
const int M = 1e9 + 7;
using namespace std;
mt19937_64 rng(time(0));
int n, m;
ll dp[maxn][maxn];
char s[maxn][maxn];

void palin() {
    int len = (m + n) / 2 - 1;
    fi(a, 1, len) {
        fid(i, m, 1) {
            int j = a - i + 2;
            if (j < 1 || j > n) continue;
            fi(u, 1, m) {
                int v = m + n - u - a;
                if (v < 1 || v > n) continue;
                if (s[i][j] != s[u][v]) { dp[i][u] = 0; continue; }
                dp[i][u] = (dp[i][u] + dp[i - 1][u] + dp[i][u + 1] + dp[i - 1][u + 1]) % M;
            }
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cin >> m >> n;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) cin >> s[i][j];
    if (s[1][1] != s[m][n]) { cout << 0; return 0; }
    dp[1][m] = 1;
    palin();
    ll res = 0;
    fi(i, 1, m) res = (res + dp[i][i]) % M;
    if ((m + n) % 2) fi(i, 1, m - 1) res = (res + dp[i][i + 1]) % M;
    cout << res;
    return 0;
}

## B. Khó Hiểu Xâu

Gọi hai xâu cần so sánh là $S$ và $T$ có độ dài $len$.
Gọi $S_a$ là xâu mà $S_a[i]$ = $1$ nếu $S_i$ = $a$, ngược lại $S_a[i]$ = $0$.
Giả sử $f(a) = c$ (mỗi $a$ ở $S$ thì bằng $c$ ở $T$, và mỗi $c$ ở $T$ thì bằng $a$ ở $S$) thì ta thấy $S_a$ = $T_c$.
Do đó $26$ xâu ở $S$ hợp với $26$ xâu ở $T$ phải tạo thành các cặp xâu bằng nhau, sao cho không xâu nào không được ghép cặp, và mỗi xâu chỉ thuộc duy nhất một cặp. ($A$)
Để so sánh hai xâu bằng nhau nhanh, thì ta dùng HASH. Để kiểm tra điều kiện ($A$) ta đơn giản là sort hai dãy lại, rồi kiểm tra xem hai dãy có giống nhau không.

#include <bits/stdc++.h>
#define VanLoi ""
#define gb(i, j) ((i >> j) & 1)
 
using namespace std;
 
const int N = (int)2e5 + 5, MOD = (int)1e9 + 7, mod = (int)1e9 + 20041203;
 
const int base = 31, BASE = 37;
 
int n, m, h[N][30], H[N][30], pw[N], PW[N];
string s;
 
struct pii {
    int F, S;
    bool operator < (const pii& x) const {
        if (F == x.F) return S < x.S;
        return F < x.F;
    }
};
 
pii get(int l, int r, int state) {
    int x = (1ll * h[r][state] - 1ll * h[l - 1][state] * pw[r - l + 1] + 1ll * mod * mod) % mod;
    int y = (1ll * H[r][state] - 1ll * H[l - 1][state] * PW[r - l + 1] + 1ll * MOD * MOD) % MOD;
    return { x, y };
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    cin >> s;
    s = ' ' + s;
    pw[0] = PW[0] = 1;
    for (int i = 1; i <= n; i++) {
        pw[i] = 1ll * pw[i - 1] * base % mod;
        PW[i] = 1ll * PW[i - 1] * BASE % MOD;
        for (int j = 0; j <= 25; j++) {
            int val = 0;
            if (s[i] - 'a' == j) val = 1;
            h[i][j] = (1ll * h[i - 1][j] * base + val) % mod;
            H[i][j] = (1ll * H[i - 1][j] * BASE + val) % MOD;
        }
    }
    while (m--) {
        int x, y, len;
        cin >> x >> y >> len;
        vector <pii> vec_x, vec_y;
        for (int i = 0; i <= 25; i++) {
            vec_x.push_back(get(x, x + len - 1, i));
            vec_y.push_back(get(y, y + len - 1, i));
        }
        sort(vec_x.begin(), vec_x.end());
        sort(vec_y.begin(), vec_y.end());
        bool ok = true;
        if (vec_x.size() != vec_y.size()) ok = false; else {
            for (int i = 0; i < (int)vec_x.size(); i++) if (vec_x[i].F != vec_y[i].F || vec_x[i].S != vec_y[i].S) {
                ok = false;
                break;
            }
        }
        if (ok) cout << "YES\n"; else cout << "NO\n";
    }
}

## C. Dãy số của Trung

$f(l, r)$ = $\sum\limits_{i=1}^{r - l + 1} a_i \cdot i$ = $\sum\limits_{i=1}^{r - l + 1} a_i$ $\cdot$ (số thằng < $a_i$ + $1$). ($A$)
Với $i$, giá trị $a_i$, xét một thằng nhỏ hơn nó bên trái: $j < i$ và $a_j < a_i$, để thằng $j$ donate vào đáp án thì $j$ và $i$ phải cùng thuộc một $l, r$.
=> $l$ sẽ giao động từ $1$ đến $j$, $r$ sẽ giao động từ $i$ đến $n$.
=> số cách là $j \cdot (n - i + 1)$.
Với mỗi cách này, dựa vào công thức ($A$) ta thấy đáp án sẽ tăng lên $a_i \cdot 1$ = $a_i$.
Vậy $ans$ += $a_i \cdot j \cdot (n - i + 1)$ .
Ta thấy $a_i \cdot (n - i + 1)$ cố định, còn $j$ ta có thể dùng IT hoặc BIT để tính.
Tương tự với một thằng nhỏ hơn $a_i$ bên phải $i$.

#include <bits/stdc++.h>
#define VanLoi ""
#define gb(i, j) ((i >> j) & 1)
 
using namespace std;
 
const int N = (int)5e5 + 5, MOD = (int)1e9 + 7, mod = (int)1e9 + 20041203;
 
int n, res, sum[N * 4][2];
 
void add(int& x, int y) {
    x += y;
    if (x >= MOD) x -= MOD;
}
 
struct pii {
    int F, S;
    bool operator < (const pii& x) const {
        return F < x.F;
    }
} a[N];
 
void ud(int id, int l, int r, int pos) {
    add(sum[id][0], pos);
    add(sum[id][1], n - pos + 1);
    if (l == r) return;
    int m = (l + r) >> 1;
    if (pos <= m) ud(id << 1, l, m, pos);
    else ud(id << 1 | 1, m + 1, r, pos);
}
 
int get(int id, int l, int r, int d, int c, int state) {
    if (r < d || l > c) return 0;
    if (d <= l && r <= c) return sum[id][state];
    int m = (l + r) >> 1;
    int x = get(id << 1, l, m, d, c, state);
    add(x, get(id << 1 | 1, m + 1, r, d, c, state));
    return x;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i].F, a[i].S = i;
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        /// trái
        int ans = 1ll * get(1, 1, n, 1, a[i].S, 0) * (n - a[i].S + 1) % MOD;
        
        /// phải
        ans = (1ll * get(1, 1, n, a[i].S, n, 1) * a[i].S + ans) % MOD;
        
        /// chính nó
        ans = (1ll * a[i].S * (n - a[i].S + 1) + ans) % MOD;
        res = (1ll * ans * a[i].F + res) % MOD;
        ud(1, 1, n, a[i].S);
    }
    cout << res;
}