Problem T1: Maximum Cross-Shaped Area in a Grid

Given a binary grid where '.' represents a valid cell and other characters are blocked, compute the largest cross-shaped region centered at any valid cell. A cross is defined by a vertical segment of height h and a horizontal segment of width w, both centered at the same point, with the total perimeter being 2(h + w) - 1.

We preprocess a height array h[i][j] representing the number of consecutive '.' characters ending at cell (i, j) from above. For each cell (i, j) with non-zero hieght, we expand left and right as long as the height in the current row is at least as large as the current center height. This ensures the cross remains valid horizontally. The maximum perimeter encountered during this scan is the answer.

int n, m;
char grid[550][550];
int height[550][550];
int maxPerimeter = 0;

for (int i = 1; i <= n; ++i) {
    scanf("%s", grid[i] + 1);
    for (int j = 1; j <= m; ++j) {
        if (grid[i][j] == '.') {
            height[i][j] = height[i-1][j] + 1;
        } else {
            height[i][j] = 0;
        }
    }
}

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        if (height[i][j] == 0) continue;
        int baseHeight = height[i][j];
        int left = j, right = j;
        
        // Expand right while height allows
        while (right < m && height[i][right + 1] >= baseHeight) ++right;
        
        // Expand left while height allows
        while (left > 1 && height[i][left - 1] >= baseHeight) --left;
        
        int width = right - left + 1;
        maxPerimeter = max(maxPerimeter, 2 * (width + baseHeight) - 1);
    }
}

Problem T2: Linear Recurrence with Matrix Exponentiation

A recurrence relation is defined over states cnt[i][0] and cnt[i][1], tracking the number of ways to reach step i with state 0 or 1, and g[i][0], g[i][1] storing accumulated weights. Transitions depend on three offsets a, b, c, and two constants d, e.

Since a, b, c ≤ 30, the recurrence only depends on the previous 30 states. We construct a state vector of size 124, encoding the last 31 values of cnt[i][0], cnt[i][1], g[i][0], and g[i][1]. A 124×124 transformation matrix is built to shift the window forward by one step and compute new values using the recurrence rules.

For n > 30, we compute the state at step 30 using DP, then apply matrix exponentiation to jump directly to step n. The final answer is the sum of the last two components of the resulting state vector.

struct Matrix {
    int mat[205][205];
    Matrix() { memset(mat, 0, sizeof(mat)); }
    
    Matrix operator*(const Matrix& other) const {
        Matrix res;
        for (int i = 1; i <= 130; ++i)
            for (int j = 1; j <= 130; ++j)
                for (int k = 1; k <= 130; ++k)
                    res.mat[i][j] = (res.mat[i][j] + mat[i][k] * other.mat[k][j]) % mod;
        return res;
    }
    
    void identity() {
        for (int i = 1; i <= 190; ++i) mat[i][i] = 1;
    }
};

Matrix power(Matrix base, int exp) {
    Matrix result; result.identity();
    while (exp) {
        if (exp & 1) result = result * base;
        base = base * base;
        exp >>= 1;
    }
    return result;
}

// Precompute initial states for i in [0, 30]
// Build transition matrix B based on recurrence rules
// Multiply initial state vector by B^(n-30) for n > 30

Problem T3: Trie-Based Greedy Deletion with DFS

Two sets of strings are given. The first set is inserted into a trie, recording the number of times each node is visited (tim[u]). The second set is used to mark the size of the subtree rooted at each node (sz[u]) by traversing each string and incrementing the count at its terminal node.

We perform a DFS on the trie. For each node, we aggregate subtree counts and then greedily match as many deletions as possible: if the subtree size is greater than or equal to the visit count, we delete all visits and reduce the subtree size accordingly; otherwise, we delete the entire subtree. The total cost is the sum of depths multiplied by the number of deletions performed at each node.

int trie[1000005][26], depth[1000005], visitCount[1000005], subtreeSize[1000005], deleted[1000005];
int nodeCount = 0;

void insertFirst(const string& s) {
    int cur = 0;
    for (char c : s) {
        int idx = c - 'a';
        if (!trie[cur][idx]) {
            trie[cur][idx] = ++nodeCount;
            depth[nodeCount] = depth[cur] + 1;
        }
        cur = trie[cur][idx];
        ++visitCount[cur];
    }
}

void insertSecond(const string& s) {
    int cur = 0;
    for (char c : s) {
        int idx = c - 'a';
        if (!trie[cur][idx]) break;
        cur = trie[cur][idx];
    }
    ++subtreeSize[cur];
}

int totalCost = 0;

void dfs(int node) {
    for (int i = 0; i < 26; ++i) {
        if (trie[node][i]) {
            dfs(trie[node][i]);
            subtreeSize[node] += subtreeSize[trie[node][i]];
            deleted[node] += deleted[trie[node][i]];
        }
    }
    
    int remaining = visitCount[node] - deleted[node];
    if (subtreeSize[node] >= remaining) {
        totalCost += remaining * depth[node];
        subtreeSize[node] -= remaining;
        deleted[node] += remaining;
    } else {
        totalCost += subtreeSize[node] * depth[node];
        deleted[node] += subtreeSize[node];
        subtreeSize[node] = 0;
    }
}

Problem T4: Range Updates with Modular Exponentiation and Meet-in-the-Middle

Each element a[i] is subject to range updates that apply the transformation x → x³ mod v. Since repeated cubing modulo v eventually cycles, and by the pigeonhole principle, any interval longer than 14 will always have a subset summing to zero modulo v, we only need to check intervals of length ≤ 14.

We precompute a DP table dp[x][j] representing x^(3^j) mod v using doubling. A segment tree tracks the number of operations applied to each element. For queries, we first retrieve the current value of each element in the range, then use meet-in-the-middle to check if any subset sums to zero modulo v.

int dp[1005][21]; // dp[x][j] = x^(3^j) mod v
void precompute() {
    for (int x = 0; x < v; ++x) dp[x][0] = (1LL * x * x % v) * x % v;
    for (int j = 1; j <= 20; ++j)
        for (int x = 0; x < v; ++x)
            dp[x][j] = dp[dp[x][j-1]][j-1];
}

struct SegmentTree {
    int tag[N << 2];
    void push(int k) {
        if (tag[k]) {
            tag[lc] += tag[k];
            tag[rc] += tag[k];
            tag[k] = 0;
        }
    }
    void update(int k, int l, int r) { /* range increment */ }
    void query(int k, int l, int r) { /* apply exponentiation and retrieve values */ }
};

// For query [l, r] with len ≤ 14:
// Split into two halves, compute all subset sums for each half
// Use hash set to check if any pair sums to 0 mod v