# **LQDOJ Cup 2023 - Round 2 - Durian**

## Subtask 1:
- Sinh nhị phân $2^n$ trường hợp, với bit thứ $i = 1$ thì sóc sẽ hải quả đó và ngược lại.
- DFS kiểm tra thỏa mãn yêu cầu đề bài.
- Đáp án là trường hợp thảo mãn yêu cầu có nhiều bit $1$ nhất.
- Độ phức tạp là $\mathcal{O}(2^n ⋅ n)$.

namespace sub1 {
    const int N = 21;
    int dist[N][N];
    bool mark[N];
    int res;

    void dfs(int u, int p, int s, int d) {
        for (int v : adj[u]) if (v != p) {
            dist[s][v] = d + 1;
            dfs(v, u, s, d+1);
        }
    }

    void backtrack(int p, int cnt) {
        if (p == n+1) {
            res = max(res, cnt);
            return;
        }
        backtrack(p+1, cnt);
        bool ok = true;
        for (int i = 1; i < p; ++i) {
            if (mark[i] && dist[i][p] < lw) {
                ok = false;
                break;
            }
        }        
        if (ok) {
            mark[p] = true;
            backtrack(p+1, cnt+1);
            mark[p] = false;
        }
    }
    
    int solve() {
        for (int i = 1; i <= n; ++i) {
            dfs(i, -1, i, 0);
        }
        res = 0;
        backtrack(1, 0);
        return res;
    }
}

## Subtask 2 + 3:
- Ở subtask này sử dụng kiến thức ***DP on tree*** để giải quyết bài toán.
- $f[u][i]$ là chọn được nhiều đỉnh nhất từ các đỉnh con đã xét, với $u$ là đỉnh hiện tại và $i$ là khoảng cách ngắn nhất từ đỉnh con được chọn đến đỉnh $u$.
- $g[i]$ là mảng phụ của $f[u][i]$ với tác dụng tạm thời khi duyệt qua cây con $v$.
- $dis[u]$ là khoảng cách dài nhất từ các đỉnh đã xét trong cây $u$ đến đỉnh $u$.

void dfs(int u, int par){
    dis[u] = 0;
    for (int v : a[u]) if (v != par){
        dfs(v,u); 
        dis[u] = max(dis[u],dis[v] + 1); 
        // cập nhật khoảng cách dis[u].
        fill(g.begin(),g.end(),0); 
        // làm sạch mảng g
        for (int i = 0 ; i <= min(d,dis[u]) ; i++){
            g[i] = dp[u][i];
            for (int j = max(i - 1,0) ; j <= min(d - 1,dis[v]) ; j++)
                g[i] = max(g[i],dp[u][max(i,d -(j + 1))] + dp[v][j]);
            /*
             g[i] là khoảng cách ngắn nhất từ các đỉnh đã chọn đến u là i,
             mình muốn khoảng cách ngắn nhất là i và đồng thời chọn thỏa mãn 
             điều kiện đề bài thì phải chia ra 3 điều kiện.
             - f[u][x] x phải lớn hơn i.
             - f[v][y] y phải lớn hơn i - 1.
             - x + (y + 1) >= d. 
             vì khi f[u][x], x càng lớn thì đáp án càng nhỏ nên mình chỉ xét 
             đúng f[u][x] với x nhỏ nhất.
             -> mình có trạng thái như trên.
             */
        }

        for (int i = 0 ; i <= min(d,dis[u]) ; i++) dp[u][i] = g[i];
        // cập nhật mảng phụ g[i] lại cho dp[u][i]
    }
    dp[u][0] = max(dp[u][0],dp[u][d] + 1);
    // khi khoảng cách ngắn nhất từ các con đến đỉnh u bằng d thì có thể 
    // chọn đỉnh u (hái trái u) khi đó khoảng cách sẽ là 0.
}

## Subtask 4:
- Mình nhận xét là khi mình chọn lần lượt các đỉnh có chiều cao từ lớn đến bé. Nếu đỉnh đó mà vẫn thỏa mãn điều kiện thì chọn không thì thôi. Thì đáp án luôn là tối ưu.

**$=>$ mình có thuật toán như sau:**
- Định nghĩa : chọn đỉnh $u$ là hái quả $u$.
- Sort các đỉnh theo chiều cao từ lớn đến bé và xét lần lượt
- gọi $value[u]$ là khoảng cách ngắn nhất từ các đỉnh của cây con $u$ được chọn đến đỉnh $u$.
- Khi mình kiểm tra điều kiện đề bài. Mình chỉ cần kiểm tra xem khoảng cách từ đỉnh mình chọn đến tất cả các đỉnh cha của nó.
- Gọi đỉnh đang xét là đỉnh $u$.
- Nếu khoảng cách từ đỉnh $u + value$ của các đỉnh cha của nó mà lớn hơn hoặc bằng $d$. Thì đỉnh này có thể chọn.

    bool get_min(int u){
        int val = 1e9 , dis = 0;
        while (u != 0){
            val = min(val,value[u] + x);
            u = par[u], dis++;
        }


        return val >= d;
    }

- Nếu chọn đỉnh đó mình sẽ làm thao tác cập nhật các value như sau:

    void update(int u){
        int val = 0; res++;
        while (u != 0){
            value[u] = min(value[u],val);
            u = par[u]; val++;
        }
    }

- với $par[u]$ là cha trực tiếp của đỉnh $u$, $par[1] = 0$.

## Subtask 5
- Nhận xét: Đáp án luôn nhỏ hơn $2*n/d + 1$. vậy nên khi $2*n/d + 1$ mà lớn hơn d thì mình làm như subtask 2 + 3.
- Ngược lại mình sẽ làm như sau:
- Vì đáp án luôn bé hơn $2*n/d + 1$ nên mình sẽ đảo nhãn của dp.Đưa đáp án làm trạng thái và đưa khoảng cách làm kết quả.
- $dp[u][i]$ với ý nghĩa có thể chọn ra i đỉnh và khoảng cách bé nhất từ các đỉnh đã chọn là con của cây con $u$ đến đỉnh $u$.

const int N = 2e5 + 100;
vector <int> a[N];
vector <vector<int> >dp;
int DP[N][450];
vector <int> g;

int n , d , res = 0, dis[N], ans = 0, cnt[N];
void dfs(int u, int par){
    dis[u] = 0;
    for (int v : a[u]) if (v != par){
        dfs(v,u); 
        dis[u] = max(dis[u],dis[v] + 1);
        fill(g.begin(),g.end(),0);
        for (int i = 0 ; i <= min(d,dis[u]) ; i++){
            g[i] = dp[u][i];
            for (int j = max(i - 1,0) ; j <= min(d - 1,dis[v]) ; j++)
                g[i] = max(g[i],dp[u][max(i,d -(j + 1))] + dp[v][j]);
        }

        for (int i = 0 ; i <= min(d,dis[u]) ; i++) dp[u][i] = g[i];
    }
    dp[u][0] = max(dp[u][0],dp[u][d] + 1);
}

void DFS(int u,int par){
    cnt[u] = 1;
    memset(DP[u],-1,sizeof(DP[u]));
    DP[u][0] = 1e9;
    for (int v : a[u]) if (v != par){
        DFS(v,u);
        cnt[u] += cnt[v];
        for (int i = 0 ; i <= ans ; i++) g[i] = DP[u][i];
        for (int i = 1 ; i <= min(ans,cnt[u]) ; i++)
            for (int j = 0 ; j <= i ; j++)
            if (g[j] != -1 && DP[v][i - j] != -1 && g[j] + DP[v][i - j] + 1 >= d) 
            {
                DP[u][i] = max(DP[u][i],min(g[j],DP[v][i - j] + 1));
            }
    }

    for (int i = 0 ; i <= min(ans,cnt[u]) ; i++) if (DP[u][i] >= d) 
        DP[u][i + 1] = max(DP[u][i + 1],0);
}

- Độ phức tạp bài : $\mathcal{O}(n⋅\sqrt{n})$.
# **LQDOJ Cup 2023 - Round 8 - Paint**
## Subtask $1$
Ta không cần quan tâm đến thứ tự dùng cây cọ mà chỉ cần dùng cọ sơn liên tiếp nhau, khi đó, đáp án là $\left\lceil\frac{n}{a + 2 \times b}\right\rceil$ (làm tròn lên).

#include <bits/stdc++.h>
/// kitsune
using namespace std;

#define fi first
#define se second
#define mp make_pair
//#define int long long
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = (int)(l); i <= (int)(r); i++)
#define per(i, r, l) for (int i = (int)(r); i >= (int)(l); i--)

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template<typename _Tp> bool minimize(_Tp& __a, const _Tp& __b) { if (__a > __b) { __a = __b; return true; } return false; }
template<typename _Tp> bool maximize(_Tp& __a, const _Tp& __b) { if (__a < __b) { __a = __b; return true; } return false; }

const int siz = 2e3 + 2;
const int SIZ = 1e6 + 2;
const int mod = 1e9 + 7;
const int maxx = 2e9;
const ll MAXX = 1e18;
const string file = "paint";

int p[siz];

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

    if (fopen((file + ".inp").c_str(), "r")) {
        freopen((file + ".inp").c_str(), "r", stdin);
        freopen((file + ".out").c_str(), "w", stdout);
    }

    int n, a, b;
    cin >> n >> a >> b;

    rep (i, 1, n) {
        cin >> p[i];
    }

    if (a + b >= n) {
        cout << 1 << "\n";
        return 0;
    }

    cout << (n + a + 2 * b - 1) / (a + 2 * b) << "\n";

//    cerr << "Time: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";

    return 0;
}

Độ phức tạp: $O(1)$.

## Subtask $2$

Nếu giá trị $w$ thoả mãn thì giá trị $w + 1$ cũng thoả mãn. Ngược lại, nếu giá trị $w$ không thoả mãn thì giá trị $w - 1$ cũng không thoả mãn. Vì vậy ta có thể sử dụng tìm kiếm nhị phân để tìm kiếm giá trị $w$ nhỏ nhất thoả mãn.

Với một giá trị $w$, ta có thể sử dụng thuật toán tham lam để kiểm tra xem có thể sơn hết các ô hay không. Ta sẽ sơn bắt đầu từ ô chưa được sơn đầu tiên, tìm ô chưa được sơn cuối cùng mà ta có thể sơn đến đó và lặp lại thuật toán ở vị trí tiếp theo.

Lưu ý, sắp xếp lại vị trí của các ô trước khi thực hiện thuật toán vì các vị trí được cho có thể chưa được sắp xếp.

Độ phức tạp: $O(n \times \log_2 10^9)$.

#include <bits/stdc++.h>
/// kitsune
using namespace std;

#define fi first
#define se second
#define mp make_pair
//#define int long long
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = (int)(l); i <= (int)(r); i++)
#define per(i, r, l) for (int i = (int)(r); i >= (int)(l); i--)

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template<typename _Tp> bool minimize(_Tp& __a, const _Tp& __b) { if (__a > __b) { __a = __b; return true; } return false; }
template<typename _Tp> bool maximize(_Tp& __a, const _Tp& __b) { if (__a < __b) { __a = __b; return true; } return false; }

const int siz = 2e3 + 2;
const int SIZ = 1e6 + 2;
const int mod = 1e9 + 7;
const int maxx = 2e9;
const ll MAXX = 1e18;
const string file = "paint";

int n, a, b;
int p[siz];

bool check(int w) {
    int cnt = 0;
    rep (i, 1, n) {
        cnt++;
        int j = i;
        while (j < n && p[j + 1] - p[i] + 1 <= w) {
            j++;
        }

        i = j;
    }

    return cnt <= a;
}

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

    if (fopen((file + ".inp").c_str(), "r")) {
        freopen((file + ".inp").c_str(), "r", stdin);
        freopen((file + ".out").c_str(), "w", stdout);
    }

    cin >> n >> a >> b;

    rep (i, 1, n) {
        cin >> p[i];
    }

    if (a + b >= n) {
        cout << 1 << "\n";
        return 0;
    }

    sort(p + 1, p + n + 1);

    int ans = -1;
    for (int lb = 1, rb = 1e9; lb <= rb; ) {
        int mb = (lb + rb) / 2;

        if (check(mb)) {
            ans = mb;
            rb = mb - 1;
        } else {
            lb = mb + 1;
        }
    }

    cout << ans << "\n";

//    cerr << "Time: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";

    return 0;
}

## Subtask $3$
Lúc này ta cần quan tâm đến thứ tự dùng cây cọ. Ta vẫn dùng tìm kiếm nhị phân như subtask 2 nhưng lúc kiểm tra, thay vì tham lam, ta sẽ sử dụng quy hoạch động.

Nếu $a + b \geq n$ thì đáp án là $1$. Sau này, giá trị của $a$ và $b$ không thể vượt quá $n$.

Gọi $dp(i, x, y)$ nghĩa là có thể sơn đến ô chưa được sơn thứ $i$ với $x$ cây cọ kích thước $w$ và $y$ cây cọ kích thước $2 \times w$ được hay không.

Có hai trường hợp:
- Chọn cây cọ kích thước $w$: $dp(j_1, x - 1, y)$.
- Chọn cây cọ kích thước $2 \times w$: $dp(j_2, x, y - 1)$.

Trong đó, $j_1$ là vị trí của ô chưa được sơn gần nhất về phía bên trái so với $i$ mà cây cọ kích thước $w$ không thể sơn từ ô $x_i$ đến ô $x_{j_1}$, tương tự với $j_2$ cho cây cọ kích thước $2 \times w$.

Kết hợp cả hai trường hợp lại, ta tính được $dp(i, x, y)$. Kết quả kiểm tra sẽ là $dp(n, x, y)$ với $0 \leq x \leq a$ và $0 \leq y \leq b$.

Độ phức tạp: $O(n^3 \times \log_2 10^9)$.

#include <bits/stdc++.h>
/// kitsune
using namespace std;

#define fi first
#define se second
#define mp make_pair
//#define int long long
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = (int)(l); i <= (int)(r); i++)
#define per(i, r, l) for (int i = (int)(r); i >= (int)(l); i--)

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template<typename _Tp> bool minimize(_Tp& __a, const _Tp& __b) { if (__a > __b) { __a = __b; return true; } return false; }
template<typename _Tp> bool maximize(_Tp& __a, const _Tp& __b) { if (__a < __b) { __a = __b; return true; } return false; }

const int siz = 2e2 + 2;
const int SIZ = 1e6 + 2;
const int mod = 1e9 + 7;
const int maxx = 2e9;
const ll MAXX = 1e18;
const string file = "paint";

int n, a, b;
int p[siz];
bool dp[siz][siz][siz];

bool check(int w) {
    memset(dp, false, sizeof(dp));
    dp[0][0][0] = true;
    rep (i, 1, n) {
        int j_1 = lower_bound(p + 1, p + n + 1, p[i] - w + 1) - p - 1;
        int j_2 = lower_bound(p + 1, p + n + 1, p[i] - 2 * w + 1) - p - 1;
        rep (x, 0, a) rep (y, 0, b) {
            if (x > 0) {
                dp[i][x][y] |= dp[j_1][x - 1][y];
            }

            if (y > 0) {
                dp[i][x][y] |= dp[j_2][x][y - 1];
            }
        }
    }

    rep (x, 0, a) rep (y, 0, b) {
        if (dp[n][x][y]) {
            return true;
        }
    }

    return false;
}

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

    if (fopen((file + ".inp").c_str(), "r")) {
        freopen((file + ".inp").c_str(), "r", stdin);
        freopen((file + ".out").c_str(), "w", stdout);
    }

    cin >> n >> a >> b;

    rep (i, 1, n) {
        cin >> p[i];
    }

    if (a + b >= n) {
        cout << 1 << "\n";
        return 0;
    }

    sort(p + 1, p + n + 1);

    int ans = -1;
    for (int lb = 1, rb = 1e9; lb <= rb; ) {
        int mb = (lb + rb) / 2;

        if (check(mb)) {
            ans = mb;
            rb = mb - 1;
        } else {
            lb = mb + 1;
        }
    }

    cout << ans << "\n";

//    cerr << "Time: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";

    return 0;
}

## Subtask $4$
Tương tự như subtask 3, thay vì lưu trạng thái $y$, ta có thể đưa nó ra ngoài.

Gọi $dp(i, x)$ là số lượng cây cọ kích thước $2 \times w$ ít nhất để sơn đến ô chưa được sơn thứ $i$ với $x$ cây cọ kích thước $w$.

Tương tự, có hai trường hợp:
- Chọn cây cọ kích thước $w$: $dp(j_1, x - 1)$.
- Chọn cây cọ kích thước $2 \times w$: $dp(j_2, x) + 1$.

Kết hợp cả hai trường hợp lại, ta tính được $dp(i, x)$. Kết quả kiểm tra sẽ là thoả mãn nếu tồn tại $x$ sao cho $0 \leq x \leq a$ và $dp(n, x) \leq b$.

Độ phức tạp: $O(n^2 \times \log_2 10^9)$.

    #include <bits/stdc++.h>
    /// kitsune
    using namespace std;
    
    #define fi first
    #define se second
    #define mp make_pair
    //#define int long long
    #define sz(x) (int)(x).size()
    #define all(x) (x).begin(), (x).end()
    #define rep(i, l, r) for (int i = (int)(l); i <= (int)(r); i++)
    #define per(i, r, l) for (int i = (int)(r); i >= (int)(l); i--)
    
    typedef long long ll;
    typedef pair<int, int> pii;
    typedef pair<ll, ll> pll;
    
    template<typename _Tp> bool minimize(_Tp& __a, const _Tp& __b) { if (__a > __b) { __a = __b; return true; } return false; }
    template<typename _Tp> bool maximize(_Tp& __a, const _Tp& __b) { if (__a < __b) { __a = __b; return true; } return false; }
    
    const int siz = 2e3 + 2;
    const int SIZ = 1e6 + 2;
    const int mod = 1e9 + 7;
    const int maxx = 2e9;
    const ll MAXX = 1e18;
    const string file = "paint";
    
    int n, a, b;
    int p[siz];
    int dp[siz][siz];
    
    bool check(int w) {
        memset(dp, 0x3f, sizeof(dp));
        dp[0][0] = 0;
        rep (i, 1, n) {
            int j_1 = lower_bound(p + 1, p + n + 1, p[i] - w + 1) - p - 1;
            int j_2 = lower_bound(p + 1, p + n + 1, p[i] - 2 * w + 1) - p - 1;
            rep (k, 0, a) {
                if (k > 0) {
                    minimize(dp[i][k], dp[j_1][k - 1]);
                }
                minimize(dp[i][k], dp[j_2][k] + 1);
            }
        }
    
        rep (k, 0, a) {
            if (dp[n][k] <= b) {
                return true;
            }
        }
    
        return false;
    }
    
    signed main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    
        if (fopen((file + ".inp").c_str(), "r")) {
            freopen((file + ".inp").c_str(), "r", stdin);
            freopen((file + ".out").c_str(), "w", stdout);
        }
    
        cin >> n >> a >> b;
    
        rep (i, 1, n) {
            cin >> p[i];
        }
    
        if (a + b >= n) {
            cout << 1 << "\n";
            return 0;
        }
    
        sort(p + 1, p + n + 1);
    
        int ans = -1;
        for (int lb = 1, rb = 1e9; lb <= rb; ) {
            int mb = (lb + rb) / 2;
    
            if (check(mb)) {
                ans = mb;
                rb = mb - 1;
            } else {
                lb = mb + 1;
            }
        }
    
        cout << ans << "\n";
    
    //    cerr << "Time: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";
    
        return 0;
    }

# **LQDOJ Cup 2023 - Round 8 - Đồ thị chữ H**
## Subtask 1: $N \le 20$
- Do $N$ nhỏ, ta có thể đơn giản duyệt để xác định từng đồ thị H là đồ thị con của $G$.
- Ta có thể phân biệt các đồ thị con chữ H thông qua "cạnh nối" (nét giữa của chữ $H$)
---
- Ta duyệt $M$ cạnh, xem hai đỉnh thuộc cạnh là $C$ và $D$, sau đó lần lượt duyệt các đỉnh kề của $C$ và $D$ trong $\mathcal{O}(N^{4})$.
- Độ phức tạp: $\mathcal{O}(M \times N^{4})$
---
## Subtask 2: $M = N-1$, đồ thị liên thông
**Nhận xét:** do mỗi cạnh trên cây đều là cầu, ta có thể chắc chắn rằng với mỗi cặp $(C, D)$ kề nhau thì chúng không có đỉnh kề chung nào.

---
Với mỗi cạnh $(u, v) \in G$, ta có thể tính số lượng đồ thị hình chữ $H$ chứa $(u, v)$ làm "cạnh nối" thông qua công thức:

$$C^{2}_{(\deg(u)-1)} \times C^{2}_{(\deg(v)-1)}$$

Với $\deg(x)$ là bậc (số cạnh kề) của đỉnh $x$.

---
- Đáp án là: $\sum\limits_{(u,v) \in E} C^{2}_{(\deg(u)-1)} \times C^{2}_{(\deg(v)-1)}$
- Độ phức tạp: $\mathcal{O}(N+M)$
---

const int N = 2e5 + 50;
vector<int> adj[N];

void solve(int testID) {
	// DBGn(testID);
	int n,m;
	cin >> n >> m;
	for (int u,v, i = 0; i < m; i++) {
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	Int ans = 0;
	for (int u = 1; u <= n; u++) {
		for (auto v : adj[u]) if (u < v) {
			int cu = adj[u].size(), cv = adj[v].size();
			Int u_trip = 1ll*(cu-1)*(cu-2) / 2;
			Int v_trip = 1ll*(cv-1)*(cv-2) / 2;
			ans += (u_trip % MOD) * (v_trip % MOD) % MOD;
		}
	}
	ans %= MOD;
	cout << ans;
}

## Subtask 3: $M, N \le 5000$
- Ta nhận thấy, khi áp dụng công thức tương tự như subtask 2 thì xuất hiện một số trường hợp $(u, v)$ cùng chọn 1, 2 đỉnh kề chung.
- Do đó ta cần dùng bao hàm loại trừ để khử các trường hợp này.
---
- Gọi `common` là số đỉnh kề chung của $(u, v)$, ta có thể đếm trong $O(N)$.
- Bao hàm loại trừ:
- Cộng tất cả cách chọn của $(u, v)$ $(F_0)$
- Trừ số trường hợp $(u, v)$ dùng 1 đỉnh kề chung $(F_{1})$
- Cộng số trường hợp $(u, v)$ dùng 2 đỉnh kề chung $(F_{2})$
---
- $F_{0}(u, v)= C^{2}_{(\deg(u)-1)} \times C^{2}_{(\deg(v)-1)}$
- $F_{1}(u, v) = (deg(u)-2) \times (\deg(v) -2) \times \text{common}$
- $F_{2}(u, v) = \cfrac{(\text{common}-1)\times \text{common}}{2}$
- Đáp án: $\sum\limits_{(u, v)\in E} F_{0}(u, v) - F_{1}(u, v) + F_{2}(u, v)$

- Độ phức tạp: $\mathcal{O}(M \times N)$

#include<bits/stdc++.h>

using namespace std;
#define N 100010
#define ll long long
#define ii pair<int,int>
#define fs first
#define sc second
#define pb push_back
#define iii pair<int,ii>
#define int ll

const ll mod=1e9+7;
int ans=0,n,m,dem,id[N],divide2;
ii edge[200010];
bitset<N>bit[505];
vector<int>g[N];

void selfadd(int&u,int v)
{
    u=(u+v)%mod;
}

ll mu(ll x,ll y)
{
    ll res=1;
    for(;y>0;y>>=1,x=x*x%mod)
        if(y&1)
            res=res*x%mod;
    return res;
}

int32_t main()
{
    freopen("HGRAPH.inp","r",stdin);
    freopen("HGRAPH.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        edge[i]={u,v};
        g[u].pb(v);
        g[v].pb(u);
    }
    for(int i=1;i<=n;i++)
        sort(g[i].begin(),g[i].end());
    for(int i=1;i<=n;i++)
        if((int)g[i].size()*(int)g[i].size()>m*2)
        {
            id[i]=++dem;
            for(auto v:g[i])
                bit[dem][v]=1;
        }
    divide2=mu(2,mod-2);
    for(int i=1;i<=m;i++)
    {
        int u=edge[i].fs,v=edge[i].sc;
        if(g[u].size()>g[v].size())
            swap(u,v);
        int L=g[u].size()-1,R=g[v].size()-1,giao=0;
        {
            int pos=0;
            for(auto x:g[u])
            {
                while(pos<g[v].size() && g[v][pos] < x)
                    pos++;
                if(pos < g[v].size() && g[v][pos] == x)
                {
                    giao++;
                    pos++;
                }
            }
        }
        selfadd(ans,L*(L-1)%mod*divide2%mod*R%mod*(R-1)%mod*divide2);
        selfadd(ans,-giao*(L-1)*(R-1));
        selfadd(ans,giao*(giao-1)/2);
    }
    cout<<(ans+mod*mod)%mod;
    return 0;
}

---

## Subtask 4: $N \le 10^{4}, M \le 4 \cdot 10^{5}$
- Ta không thể đếm số đỉnh kề của từng cặp đỉnh $(u, v)$ vì sẽ dẫn đến `TLE`.
---
- Ta dùng `std::bitset<N> adj[N];` để lưu ma trận kề của từng đỉnh.
- Để đếm số đỉnh chung, dùng toán tử `&` để lấy bit chung của hai `bitset`, sau đó dùng hàm `count()` để đếm số bit `1`.
-

int common = (adj[u] & adj[v]).count();
...

---
- Độ phức tạp của phép `&` của `bitset` là $\mathcal{O}(\frac{N}{64})$
- Độ phức tạp: $\mathcal{O}(M \times \frac{N}{64})$

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include<bits/stdc++.h>
using namespace std;

#define all(v) (v).begin(), (v).end()
#define cst(T) const T&

template<class A, class B> bool umin(A& var, cst(B) val) {
	return (val < var) ? (var = val, true) : false;
}
template<class A, class B> bool umax(A& var, cst(B) val) {
	return (var < val) ? (var = val, true) : false;
}

typedef long long Int;
typedef long double Real;
// const int MOD = 2004010501;
const int MOD = 1e9 + 7;
void add(int &a, const int& b) { 
	if ((a+=b) >= MOD) a -= MOD; 
	if (a < 0) a += MOD;
}
int product(const int& a, const int& b) { return (Int)a*b % MOD; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class X, class Y> Int random(const X& l, const Y& r) {
	return uniform_int_distribution<Int>(l,r)(rng);
}
#define DBG(x) cerr << #x << " = " << x << ' ';
#define DBGn(x) cerr << #x << " = " << x << '\n';

template<typename T> vector<T> readInput(int n) {
	vector<T> v(n); for (auto &vi : v) cin >> vi; return v;
}

const int N = 1e4 + 10;
vector<int> adj[N];
bitset<N> neighbor[N];

int choose_2(int n) { return (n < 2) ? 0 : 1ll*n*(n-1) / 2 % MOD; }

void solve(int testID) {
	// DBGn(testID);
	int n,m;
	cin >> n >> m;
	for (int u,v, i = 0; i < m; i++) {
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
		neighbor[u][v] = neighbor[v][u] = 1;
	}
	int ans = 0;
	for (int u = 1; u <= n; u++) {
		for (auto v : adj[u]) if (u < v) {
			int c_u = adj[u].size(), c_v = adj[v].size();
			c_u -= 1, c_v -= 1; // exclude (u,v)
			int common = (neighbor[u] & neighbor[v]).count();
			// cerr << "(" << u << ',' << v << ") - > " << c_u << ',' << c_v << " and " << common << '\n';
			int u_out2 = choose_2(c_u - common);
			int v_out2 = choose_2(c_v - common);
			// all 4 outside
			add(ans, product(u_out2, v_out2));
			// one pick 2, another pick 0 (pick is pick outside)
			add(ans, product(u_out2, choose_2(common)));
			add(ans, product(choose_2(common), v_out2));
			// one pick 2, another pick 1?
			int v_mix = product(common, c_v - common);
			int u_mix = product(common, c_u - common);
			add(ans, product(u_out2, v_mix));
			add(ans, product(u_mix, v_out2));
			// both pick 1? (2 in, 2 out)
			add(ans, product(product(common, common-1), product(c_u - common, c_v - common)));
			// one pick 1, another pick 0? (3 inside, 1 out)
			int in2 = choose_2(common);
			add(ans, product(product(c_u - common, common - 2), in2));
			add(ans, product(product(c_v - common, common - 2), in2));
			// both pick 0 (all 4 inside)
			add(ans, product(choose_2(common), choose_2(common-2)));
		}
	}
	ans %= MOD;
	cout << ans;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	#define task "hgraph"
	if (fopen(task".inp", "r")) {
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}
	int numTests = 1;
	// cin >> numTests;
	for (int i = 1; i <= numTests; i++) solve(i);
}

---
## Subtask 5: $N \le 10^{5}, M \le 4 \cdot 10^5$
- **Nhận xét:** Việc đếm số đỉnh chung bị chậm khi ta duyệt danh sách kề của các đỉnh có bậc to.
---
- Ta chia $N$ đỉnh thành 2 loại:
- Đỉnh to: có bậc $> \sqrt{M}$
- Đỉnh nhỏ: có bậc $\le \sqrt{M}$
- Với đỉnh to, ta lưu ma trận kề bằng `bitset`.
- Với đỉnh nhỏ, ta lưu danh sách kề bằng `vector`.
---
Với mỗi cạnh $(u, v)$, có 3 trường hợp xảy ra:
1. **Nhỏ - nhỏ**: ta có thể duyệt danh sách kề và kiểm tra trong $\mathcal{O}(\sqrt{M})$ bằng kĩ thuật hai con trỏ (sau khi sắp xếp danh sách kề).
2. **To - nhỏ**: duyệt danh sách kề của đỉnh nhỏ, và kiểm tra bằng `bitset` của đỉnh to, $\mathcal{O}(\sqrt{M})$.
3. **To - to**: Dùng toán tử `&` như subtask 4 để xác định đỉnh kề chung trong $\mathcal{O}(\frac{N}{64})$.
---
- Có tối đa $\sqrt{M}$ đỉnh to $\to$ tối đa $C^{2}_{\sqrt{M}} \approx \frac{M}{2}$ cạnh (to - to).
- Do đó tổng độ phức tạp của trường hợp 3 là $\mathcal{O}\left(\frac{M}{2} \cdot \frac{N}{64}\right)= \mathcal{O}\left(\frac{MN}{128}\right)$
- Độ phức tạp: $\mathcal{O}(M \sqrt{M} + \frac{MN}{128})$

#include<bits/stdc++.h>

using namespace std;
#define N 100010
#define ll long long
#define ii pair<int,int>
#define fs first
#define sc second
#define pb push_back
#define iii pair<int,ii>
#define int ll

const ll mod=1e9+7;
int ans=0,n,m,dem,id[N],divide2;
ii edge[400010];
bitset<N>bit[505];
vector<int>g[N];

void selfadd(int&u,int v)
{
    u=(u+v)%mod;
}

ll mu(ll x,ll y)
{
    ll res=1;
    for(;y>0;y>>=1,x=x*x%mod)
        if(y&1)
            res=res*x%mod;
    return res;
}

int32_t main()
{
    freopen("HGRAPH.inp","r",stdin);
    freopen("HGRAPH.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        edge[i]={u,v};
        g[u].pb(v);
        g[v].pb(u);
    }
    for(int i=1;i<=n;i++)
        sort(g[i].begin(),g[i].end());
    for(int i=1;i<=n;i++)
        if((int)g[i].size()*(int)g[i].size()>m*2)
        {
            id[i]=++dem;
            for(auto v:g[i])
                bit[dem][v]=1;
        }
    divide2=mu(2,mod-2);
    for(int i=1;i<=m;i++)
    {
        int u=edge[i].fs,v=edge[i].sc;
        if(g[u].size()>g[v].size())
            swap(u,v);
        int L=g[u].size()-1,R=g[v].size()-1,giao=0;
        if(id[u]==0 && id[v]!=0)// small -> big
        {
            for(auto x:g[u])
                if(bit[id[v]][x]==1)
                    giao++;
        }
        if(id[u]!=0 && id[v]!=0)
        {
            giao=(bit[id[u]] & bit[id[v]]).count();
        }
        if(id[u]==0 && id[v]==0)//small -> small
        {
            int pos=0;
            for(auto x:g[u])
            {
                while(pos<g[v].size() && g[v][pos] < x)
                    pos++;
                if(pos < g[v].size() && g[v][pos] == x)
                {
                    giao++;
                    pos++;
                }
            }
        }
        selfadd(ans,L*(L-1)%mod*divide2%mod*R%mod*(R-1)%mod*divide2);
        selfadd(ans,-giao*(L-1)*(R-1));
        selfadd(ans,giao*(giao-1)/2);
    }
    cout<<(ans+mod*mod)%mod;
    return 0;
}

---

# **LQDOJ Cup 2023 - Round 8 - Squirrel**
## Subtask 1:
- Vì khi đi ra từ $0$ ở thời điểm $x$ và $x + t$ đều sẽ bị trộm tại các địa điểm như nhau nên mình chỉ xét các vị trí $x < t$ sau đó dễ dàng tính trong $𝑂(1)$
Độ phức tạp: $𝑂(1)$.

    long long dis = h;
    long long tmp = ((h-1)/t);
    res = tmp*g + h;
    cout << res;

## Subtask 2:
- Nhận xét : mình có thể dừng lại ở bất cứ đâu mà không ảnh hưởng đến kết quả cuối cùng của bài toán
Gọi tổng số quả bị mất và bị trộm là cost
Mình sẽ quy hoạch đông với $f[i][j]$ là cost nhỏ nhất khi đi từ 1 đến vị trí $i$ với thời gian khi mod $t$ dư $j$:

minimize(dp[i + 1][(j + 1) % t], dp[i][j] + 1 + (j + 1 == t && !guard[i + 1] ? g : 0));
minimize(dp[i][(j + 1) % t], dp[i][j] + 1 + (j + 1 == t && !guard[i] ? g : 0));

namespace sub2 {
    int dp[1005][2005];
    bool x[1005];
    void Solve() {
        memset(dp, 63, sizeof dp);
        for (int i = 1; i <= n; i++)
            x[a[i]] = 1;
        x[h] = 1;
        dp[0][0] = 0;
        for (int i = 1; i <= h; i++) {
            for (int j = 0; j < t; j++)
                dp[i][j] = dp[i][j + t] = dp[i - 1][(j - 1 + t) % t] + 1 + (j == 0 && !x[i] ? g : 0);
            for (int j = 1; j < 2 * t; j++)
                dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1 + (j == t && !x[i] ? g : 0));
            for (int j = 0; j < t; j++)
                dp[i][j] = dp[i][j + t];
        }
        int res = dp[h + 1][0];
        for (int j = 0; j < t; j++)
            res = min(res, dp[h][j]);
        cout << res;
        exit(0);
    }
};

Độ phức tạp: $𝑂(h \cdot h)$.
## Subtask 3
- Nhân xét:
- Vì theo bài toán mình chỉ dừng lại trên các trạm bảo vệ, nên mình sẽ chỉ quan tâm đến các trạm bảo vệ đó.
- Khi bạn chủ động dừng tại trạm bảo vệ bất kì thì trong lúc dừng bạn phải dừng vào thời gian chia hết cho t (bị trộm).

- Vì vậy mình sẽ đi từ trạm $i$ đến trạm $j$ và đợi đến khi thời gian chia hết cho $t$.
- Dựa vào đó mình gọi $dp[i]$ là cost nhỏ nhất khi đến vị trí $i$ có thời gian chia hết cho $t$

dp[i] = min(dp[i],dp[j] + ((a[i] - a[j] - 1)/t)*g 
                        + (((a[i] - a[j] + t - 1)/t)*t))

Với : 
  * mọi j < i
  * ((a[i] - a[j] - 1)/t)*g là tổng số quả bị trộm khi đi từ trạm j đến i
  * (((a[i] - a[j] + t - 1)/t)*t)) là thời gian đi và dừng giữa trạm j và i
  

- Đáp án:
Bởi vì mình chỉ duyệt đến các trạm bảo vệ mà không duyệt đến h nên với mỗi $dp[i]$ mình
Đi thẳng về h như subtask 1

void sub3(){
    memset(dp,0x3f,sizeof(dp));
    dp[1] = 0;
    for (int i = 2 ; i <= n ; i++) 
        for (int j = 0 ; j < i ; j++)
            dp[i] = min(dp[i],dp[j] + ((a[i] - a[j] - 1)/p)*d + (((a[i] - a[j] + p - 1)/p)*p));

    ll res = 9e18;
    for (int i = 1 ; i <= n ; i++){
        res = min(res,((b - a[i] - 1)/p)*d + b - a[i] + dp[i]);
    }

    cout << res;
}

## Subtask 4:

- Nhận xét với các trạm có vị trí cùng số dư với $t$ mình chỉ lấy giá trị $dp$ từ trạm gần nhất với vị trí đang đứng mà không cần tới những trạm xa hơn
- Dùng mảng $g[z]$ với ý nghĩa $g[z]$ là trạm gần nhất mà $a[g[z]] % t = z$
Thay vì duyệt qua tất cả $j < i$ thì mình chỉ cần duyệt mảng $g$
- Độ Phức tạp : $𝑂(q \cdot t)$.

namespace subtask_4 {

ll dp[102];
int last[102];

void main() {
    dp[0] = 0;
    rep (i, 1, n) {
        dp[i] = MAXX;
        rep (j, 0, p - 1) {
            int l = last[j];
            minimize(dp[i], dp[l] + (a[i] - a[l] + p - 1) / p * p + (a[i] - a[l] - 1) / p * d);
        }

        last[a[i] % p] = i;
    }

    ll ans = MAXX;
    rep (i, 0, n) {
        minimize(ans, dp[i] + (b - a[i]) + ((b - a[i] - 1) / p) * d);
    }

    cout << ans << "\n";
}

}

## Subtask 5
- Dựa vào sub 4 lưu mảng $g$ bằng segment tree để lấy trạng thái trong $O(log)$ thay vì $O(n)$
- Với 2 trạm $y$ và mọi $x$ với $(x < y)$.

- Gọi  My = (a[y] – 1 + t) % t, if (My == 0) My = t
       Mx = a[x] % t,           if (Mx == 0) Mx = t
       Val = dp[x] - ((a[x] + t - 1)/t)*g - ((a[x] + t - 1)/t)*t

- Với Mx <= My:
       dp[y] = Min(dp[y], val + ((a[y] - 1 + t - 1)/t)*g + ((a[y] - 1 + t - 1)/t + 1)*t)
- Với Mx > My: 
       dp[y] = Min(dp[y], val + ((a[y] - 1)/t)*g + ((a[y] - 1)/t + 1)*t))

- Với mọi $Mx <= My$ thì **$((a[y] - 1 + t - 1)/t)*g + ((a[y] - 1 + t - 1)/t + 1)*t)$** đều giống nhau.

- Với mọi $Mx > My$ thì ***$((a[y] - 1)/t)*g + ((a[y] - 1)/t + 1)*t))$*** đều giống nhau.

- Nên ta Sử dụng Segment Tree để lưu $Val$ và get giá trị $Val_{ min}$ trong 2 khoảng $[1;My]$ và $[My + 1;t]$

#include <bits/stdc++.h>
#define ll long long 
#define int ll
using namespace std;
const int N = 1e5 + 100;
const ll LNF = 7e18;

struct segmenttree
{
    struct node
    {
        int l , r;
        ll val;
        node() {}
        node(int l , int r , ll val): l(l), r(r), val(val){}
    };

    node f[20000100];
    int n, cnt;

    void built(int _n = 0){
        n = _n;
        f[0] = node(-1,-1,LNF);
        cnt = 0;
    }

    void update(int i , int l , int r , int x , ll val){
        if (l > x || r < x) return ;

        if (l == r){
            f[i].val = min(f[i].val,val);
            return ;
        }

        int m = (l + r) >> 1;

        if (f[i].l == -1){
            f[i].l = ++cnt;
            f[cnt] = node(-1,-1,LNF);
            f[i].r = ++cnt;
            f[cnt] = node(-1,-1,LNF);
        }

        if (x <= m)  update(f[i].l,l,m,x,val);
        else update(f[i].r,m+1,r,x,val);

        f[i].val = min(f[f[i].l].val,f[f[i].r].val);
    }

    ll get(int i , int l , int r , int d , int c){
        if (d > c || l > c || d > r || i == -1) return LNF;
        if (d <= l && r <= c) return f[i].val;
        int m = (l + r) >> 1;
        return min(get(f[i].l,l,m,d,c),get(f[i].r,m+1,r,d,c));
    }
};

ll dp[N];
ll n, b , p ,d , a[N];
segmenttree IT;

void sub234(){
    memset(dp,0x3f,sizeof(dp));
    dp[1] = 0;
    for (int i = 2 ; i <= n ; i++) 
        for (int j = 0 ; j < i ; j++)
            dp[i] = min(dp[i],dp[j] + ((a[i] - a[j] - 1)/p)*d + (((a[i] - a[j] + p - 1)/p)*p));

    ll res = 9e18;
    for (int i = 1 ; i <= n ; i++){
        res = min(res,((b - a[i] - 1)/p)*d + b - a[i] + dp[i]);
    }

    cout << res;
}

void subfinal(){
    memset(dp,0x3f,sizeof(dp));
    IT.built(p);
    dp[1] = 0;
    IT.update(0,1,p,p,0);
    for (int i = 2 ; i <= n ; i++){
        ll x = ((a[i] - 1 + p) % p);
        if (x == 0) x = p;
        dp[i] = min(dp[i],IT.get(0,1,p,1,x) + ((a[i] - 1 + p - 1)/p)*d + ((a[i] - 1 + p - 1)/p + 1)*p);
        dp[i] = min(dp[i],IT.get(0,1,p,x + 1,p) + ((a[i] - 1)/p)*d + ((a[i] - 1)/p + 1)*p);
        ll y = (a[i]) % p;
        if (y == 0) y = p;
        IT.update(0,1,p,y,dp[i] - ((a[i] + p - 1)/p)*d - ((a[i] + p - 1)/p)*p);
    }

    ll res = 9e18;
    for (int i = 1 ; i <= n ; i++){
        res = min(res,((b - a[i] - 1)/p)*d + b - a[i] + dp[i]);
    }

    cout << res;
}

main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    if (fopen("Squirrel.inp","r")){
        freopen("Squirrel.inp","r",stdin);
        freopen("Squirrel.out","w",stdout);}

    cin >> b >> p >> d >> n;
    for (int i = 1 ; i <= n ; i++) cin >> a[i];

    subfinal();
   // sub234();
    return 0;
}

## Subtask 6
- Sử dụng Dynamic Segment Trees

# **LQDOJ Cup 2023 - Round 5 - Trie**

## Subtask 1
- Tạo ra mọi xâu khác nhau song xây dựng cây trie
- Vì chỉ có kí tự $a$ và $b$ nên một xâu chỉ có tối đa $2^\abs{s}$ xâu hoán vị khác nhau.
- Độ phức tạp: $\mathcal{O}(2^\abs{S} \cdot \abs{S})$.
## Subtask 2
- Sau khi phân tích bài toán mình tìm ra được công thức truy hồi như sau.
- Định nghĩa $f(x,y)$ là số đỉnh của cây trie của tất cả hoán vị của xâu ban đầu có $x$ kí tự $a$ và $y$ kí tự $b$.
- $f(0,y) = y + 1$.
- $f(x,0) = x + 1$.
- $f(x,y) = f(x - 1,y) + f(x,y - 1) + 1$.
- Công thức chỉ đúng khi mình làm với một xâu ban đầu.

ll find_f(int x,int y){
    if (x == 0 || y == 0) return max(x,y) + 1;
    int &res = f[x][y];
    if (res != -1) return res;
    res = find_f(x - 1,y) + find_f(x,y - 1) + 1;
    return res;
}

- Độ phức tạp: $\mathcal{O}(\abs{S}^2)$.

## subtask 3, 4
- Mình có thể biến đổi công thức của một xâu để áp dụng cho nhiều xâu không?
- Bài toán này mình có thể sử dụng bao hàm loại trừ để giải quyết vấn đề
- Với 2 xâu $x$ và $y$
- Mình có thể tìm $f(x_{a},x_{b})$ và $f(y_{a},y_{b})$ với $t_{a}$ là số kí tự $a$ của xâu $t$ và $t_{b}$ là số kí tự $b$ của xâu $t$
- Khi đó mình sẽ bị tính dư ra $f(min(x_{a},y_{a}),min(x_{b},y_{b}))$
$=>$ $f_{xy} = f(x_{a},x_{b}) + f(y_{a},y_{b}) - f(min(x_{a},y_{a}),min(x_{b},y_{b}))$.
- Dựa vào tính chất của bao hàm loại trừ mình cũng có thể tính được với số lượng xâu lớn hơn $2$.

    int n;
    cin >> n;
    for (int i = 1 ; i <= n ; i++){
        string s;
        cin >> s;
        a.push_back(C(0,0));
        for (char v : s) if (v == 'a') a.back().first++;
        else a.back().second++;
    }

    ll res = 0;
    for (int i = 1 ; i < (1<<n) ; i++){
        ll k = -1;
        ll A = 1e9;
        ll B = 1e9;
        for (int j = 0 ; j < n ; j++)
        if ((i>>j)&1){
            k *= -1;
            A = min(A,a[j].first);
            B = min(B,a[j].second);
        }

        res  = ((res + k*find_f(A,B) % mod) + mod) % mod ;
    }

- Độ phức tạp: $\mathcal{O}(2^n + \abs{S}^2)$.

## Subtask cuối
- Vấn đề nằm ở độ phức tạp của hàm **find_f**
- Thay vì mình quy hoạch động với độ phức tạp $n^2$ thì mình đi tìm một công thức tổng quát hơn.
- Sau khi phân tích mình tìm ra được công thức tối ưu hơn như sau:
$f(a,b) = (a + b + 2)C(b + 1) - 1$
- Ta dễ dàng tính hàm $f$ bằng tổ hợp.
- Độ phức tạp: $\mathcal{O}(2^n \cdot log(\abs{S})$.

#include <bits/stdc++.h>
#define All(x) (x).begin(),(x).end()
#define ll long long
#define C make_pair
#define TASK "trie"
using namespace std;
typedef pair<ll,ll> ii;
typedef pair<int,ii> iii;
const ll mod = 1e9 + 7;

vector <ii> a;
ll f[300100];

ll Pow(ll x, ll h){
    if (h == 0) return 1;
    if (h == 1) return x;
    ll y = Pow(x,h/2);
    if (h&1) return ((x*y%mod)*y) % mod;
    return y*y%mod;
}

ll nCk(ll x , ll y){
    if (y > x) return 0;
    return (Pow(f[y],mod - 2)*Pow(f[x - y],mod - 2) % mod)*f[x] % mod;
}
ll find_fab(int x,int y){
    return (nCk(x + y + 2,y + 1) - 1 + mod) % mod;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    if(fopen(TASK".inp", "r")){
    freopen(TASK".inp","r",stdin);
    freopen(TASK".out","w",stdout);
    }

    memset(f,-1,sizeof(f));
    f[0] = 1;
    for (int i = 1 ; i <= 200020 ; i++) f[i] = (f[i - 1]*i) % mod;
    int n;
    cin >> n;
    for (int i = 1 ; i <= n ; i++){
        string s;
        cin >> s;
        a.push_back(C(0,0));
        for (char v : s) if (v == 'a') a.back().first++;
        else a.back().second++;
    }

    ll res = 0;
    for (int i = 1 ; i < (1<<n) ; i++){
        ll k = -1;
        ll A = 1e9;
        ll B = 1e9;
        for (int j = 0 ; j < n ; j++)
        if ((i>>j)&1){
            k *= -1;
            A = min(A,a[j].first);
            B = min(B,a[j].second);
        }

        res  =((res + k*find_fab(A,B) % mod) + mod) % mod ;
    }

    cout << res;
    return 0;
}