A sequence of numbers is said to be good if it satisfies the following two conditions:

• All elements in the sequence are unique.
• If the minimum element in the sequence is a, and the maximum element in the sequence is b, then all numbers in the range [a, b] are present in the sequence. For example, (4, 2, 5, 1, 3) is a good sequence, while (2, 2, 1) or (3, 7) are not. A subsequence of an array arr is a sequence that can be derived from the array arr by deleting some or no elements without changing the order of the remaining elements. Given an array of n integers, find the number of different good subsequences. Two subsequences are considered different if they include at least one different index. For example, for the sequence (2, 2, 1), both (2, 1) formed by indices 1 and 2 and (2, 1) formed by indices 0 and 2 are considered different subsequences. Function Description Complete the function countGoodSubsequences in the editor. countGoodSubsequences has the following parameter: int arr[n]: the given array of integers Returns long integer: the number of good subsequences which can be derived from the array.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ arr[i] ≤ 10⁵, for all i

解法

"good"子序列由互不相同元素且为 [a, b] 区间内的所有整数构成(顺序任意)，因为是子序列，相对顺序与原数组一致；good 子序列中元素无重复且值集为 [a, b] 完整。统计：枚举值区间 [a, b]，再统计 arr 中能取出 a, a+1, ..., b 各一次的子序列个数。对每个值 v 出现次数 cnt[v]。对固定 [a, b]，每个值 v ∈ [a, b] 必须挑一个位置；不同位置组合即 ∏_{v=a}^{b} cnt[v]，但是子序列还要求相对顺序保持，"挑选每个值各一个位置"已经天然满足子序列定义(无论挑哪个位置都对应一个子序列)。所以答案 = Σ over [a, b] (∏ cnt[v])。可双指针扫：从 a 开始连续延伸 b 直到 v=b+1 缺失(cnt=0)。用前缀乘积 / 段乘积。时间 O(max_v)。

from collections import Counter
from typing import List

MOD = 10 ** 9 + 7

def count_good_subsequences(arr: List[int]) -> int:
    cnt = Counter(arr)
    if not cnt: return 0
    max_v = max(cnt)
    total = 0
    v = 1
    while v <= max_v:
        if cnt.get(v, 0) == 0:
            v += 1
            continue
        # find longest run [v, e] with cnt[u] > 0
        e = v
        while e + 1 <= max_v and cnt.get(e + 1, 0) > 0:
            e += 1
        # sum over [a, b] subset of [v, e]: prod cnt[a..b]
        # = sum over a from v..e of (cnt[a] * (1 + cnt[a+1] * (1 + cnt[a+2] * ...)))
        # iterate from e down
        chain = 0
        for u in range(e, v - 1, -1):
            chain = cnt[u] * (1 + chain) % MOD
            total = (total + chain) % MOD
        # subtract? No, chain already covers all [a, b] starting at u.
        # But this DOUBLE-counts because we counted each (a, b). Let's verify: chain[a] = sum over b>=a of prod cnt[a..b]. So sum chain[a] over a = total #[a,b] pairs. Good.
        v = e + 1
    return total

import java.util.*;

class Solution {
    static final long MOD = 1_000_000_007L;
    public long countGoodSubsequences(int[] arr) {
        Map<Integer, Long> cnt = new HashMap<>();
        int maxV = 0;
        for (int x : arr) { cnt.merge(x, 1L, Long::sum); maxV = Math.max(maxV, x); }
        long total = 0;
        int v = 1;
        while (v <= maxV) {
            if (cnt.getOrDefault(v, 0L) == 0) { v++; continue; }
            int e = v;
            while (e + 1 <= maxV && cnt.getOrDefault(e + 1, 0L) > 0) e++;
            long chain = 0;
            for (int u = e; u >= v; u--) {
                chain = cnt.get(u) * (1 + chain) % MOD;
                total = (total + chain) % MOD;
            }
            v = e + 1;
        }
        return total;
    }
}

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

class Solution {
    static constexpr long long MOD = 1000000007;
public:
    long long countGoodSubsequences(vector<int>& arr) {
        unordered_map<int, long long> cnt;
        int maxV = 0;
        for (int x : arr) { cnt[x]++; maxV = max(maxV, x); }
        long long total = 0;
        int v = 1;
        while (v <= maxV) {
            if (!cnt.count(v) || cnt[v] == 0) { v++; continue; }
            int e = v;
            while (e + 1 <= maxV && cnt.count(e + 1) && cnt[e + 1] > 0) e++;
            long long chain = 0;
            for (int u = e; u >= v; u--) {
                chain = cnt[u] * (1 + chain) % MOD;
                total = (total + chain) % MOD;
            }
            v = e + 1;
        }
        return total;
    }
};

Given a number line from 0 to n and a string denoting a sequence of moves, determine the number of subsequences of those moves that lead from a given point x to end at another point y. Moves will be given as a sequence of l and r instructions. An instruction l = left movement, so from position j the new position is j - 1, an instruction r = right movement, so from position j the new position would be j + 1. For example, given a number line from 0 to 6, and a sequence of moves rrlrr, the number of subsequences that lead from 1 to 4 on the number line is 3. Function Description Complete the function distinctMoves in the editor. distinctMoves has the following parameter(s):

• s: a string that represents a sequence of moves
• n: an integer that represents the upper bound of the number line
• x: an integer that represents the starting point
• y: an integer that represents the ending point Returns int: the number of distinct subsequences modulo 10⁹ + 7

Constraints

• 1 ≤ |s| ≤ 10³
• 0 ≤ x, y, n ≤ 2500

解法

DP dp[i][j] = 用 s 前 i 个字符的某个子序列，从 x 出发能到达位置 j 的方案数。转移：dp[i][j] = dp[i-1][j] + (dp[i-1][j-1] if s[i-1]=='r' else 0) + (dp[i-1][j+1] if s[i-1]=='l' else 0)，需 0 ≤ j ≤ n。最终 dp[len(s)][y]。时间 O(|s|·n)。

MOD = 10 ** 9 + 7

def distinct_moves(s: str, n: int, x: int, y: int) -> int:
    dp = [0] * (n + 1)
    dp[x] = 1
    for c in s:
        nxt = [0] * (n + 1)
        for j in range(n + 1):
            nxt[j] = dp[j]
            if c == 'r' and j > 0:
                nxt[j] = (nxt[j] + dp[j - 1]) % MOD
            if c == 'l' and j < n:
                nxt[j] = (nxt[j] + dp[j + 1]) % MOD
        dp = nxt
    return dp[y]

class Solution {
    static final long MOD = 1_000_000_007L;
    public int distinctMoves(String s, int n, int x, int y) {
        long[] dp = new long[n + 1];
        dp[x] = 1;
        for (char c : s.toCharArray()) {
            long[] nxt = dp.clone();
            for (int j = 0; j <= n; j++) {
                if (c == 'r' && j > 0) nxt[j] = (nxt[j] + dp[j - 1]) % MOD;
                if (c == 'l' && j < n) nxt[j] = (nxt[j] + dp[j + 1]) % MOD;
            }
            dp = nxt;
        }
        return (int) dp[y];
    }
}

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

class Solution {
    static constexpr long long MOD = 1000000007;
public:
    int distinctMoves(string s, int n, int x, int y) {
        vector<long long> dp(n + 1, 0);
        dp[x] = 1;
        for (char c : s) {
            vector<long long> nxt = dp;
            for (int j = 0; j <= n; j++) {
                if (c == 'r' && j > 0) nxt[j] = (nxt[j] + dp[j - 1]) % MOD;
                if (c == 'l' && j < n) nxt[j] = (nxt[j] + dp[j + 1]) % MOD;
            }
            dp = nxt;
        }
        return (int) dp[y];
    }
};

A school in HackerLand organized a scholarship exam with this interesting mathematics problem on addition. Given a string num that consists of digits ('0' to '9'), a '+' can be inserted between its characters. No adjacent '+' characters are allowed. The value of the expression is then evaluated. Find the sum of the values of all possible expressions after inserting '+' characters any number of times (possibly zero). Since the answer can be large, return the value modulo (10⁹ + 7). Function Description Complete the function getExpressionSums in the editor below. getExpressionSums has the following parameter(s):

Constraints

An unknown myth for now

Example 1

Input:

num = "123"

Output:

168

Explanation: All possible valid expressions are shown.

• "1 + 23", value = 24
• "12 + 3", value = 15
• "1 + 2 + 3", value = 6
• "123", value = 123 Their sum is 24 + 15 + 6 + 123 = 168. Thus, the answer is 168 modulo (10⁹ + 7) which is 168.

解法

考察每个数字 num[i] 对答案的总贡献。在 n-1 个空隙中各自独立决定是否加 '+'，共 2^(n-1) 种表达式。num[i] 在某段中所贡献的位权 = 10^(距离段右端)。汇总：对位置 i，遍历它在所有可能表达式中出现的"段长"。若 i 与 j 在同一段，意味着 i..j 之间无 '+'(共 j-i 个空隙都无 '+')，且 j 后面必须有 '+'(或 j == n-1)。所以贡献 = num[i] · Σ over j 10^(j-i) · 2^(其它空隙的自由选择)。复杂度 O(n²)。

MOD = 10 ** 9 + 7

def get_expression_sums(num: str) -> int:
    n = len(num)
    # pow10[k], pow2[k] precompute
    pow10 = [1] * (n + 1)
    pow2 = [1] * (n + 1)
    for i in range(1, n + 1):
        pow10[i] = pow10[i - 1] * 10 % MOD
        pow2[i] = pow2[i - 1] * 2 % MOD
    total = 0
    for i in range(n):
        # num[i] contributes when it sits at position (k from right) in its segment
        for j in range(i, n):
            d = j - i  # 10^d weight
            # gaps fixed: between i and j all "no +" (d gaps), gap after j is "+" if j < n-1 (1 gap fixed)
            fixed = d + (1 if j < n - 1 else 0)
            free = (n - 1) - fixed
            total = (total + int(num[i]) * pow10[d] % MOD * pow2[free]) % MOD
    return total

class Solution {
    static final long MOD = 1_000_000_007L;
    public int getExpressionSums(String num) {
        int n = num.length();
        long[] pow10 = new long[n + 1], pow2 = new long[n + 1];
        pow10[0] = pow2[0] = 1;
        for (int i = 1; i <= n; i++) { pow10[i] = pow10[i - 1] * 10 % MOD; pow2[i] = pow2[i - 1] * 2 % MOD; }
        long total = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int d = j - i;
                int fixed = d + (j < n - 1 ? 1 : 0);
                int free = (n - 1) - fixed;
                total = (total + (num.charAt(i) - '0') * pow10[d] % MOD * pow2[free]) % MOD;
            }
        }
        return (int) total;
    }
}

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

class Solution {
    static constexpr long long MOD = 1000000007;
public:
    int getExpressionSums(string num) {
        int n = num.size();
        vector<long long> pow10(n + 1, 1), pow2(n + 1, 1);
        for (int i = 1; i <= n; i++) { pow10[i] = pow10[i - 1] * 10 % MOD; pow2[i] = pow2[i - 1] * 2 % MOD; }
        long long total = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int d = j - i;
                int fixed_ = d + (j < n - 1 ? 1 : 0);
                int free_ = (n - 1) - fixed_;
                total = (total + (num[i] - '0') * pow10[d] % MOD * pow2[free_]) % MOD;
            }
        }
        return (int) total;
    }
};

There are employee_nodes employees in a company, out of which there are k special employees who have data network and share their mobile hotspots with other employees. There are employee_edges connections already made between the employees, where the i^th connection connects the employees employee_from[i] and employee_to[i], such that either of the employees employee_from[i] and employee_to[i] can share a mobile hotspot. Two employees x and y are connected if there is a path between them. All the employees connected to a special employee x will use the mobile hotspot of the special employee x. Up to now, to restrict data usage, any employee was connected to at most one special employee. As data consumption has increased, any employee can be connected to at most max_connections number of special employees. Find the maximum number of edges that can be added to the graph such that any employee is connected to at most max_connections special employees. Note:

• The given graph does not contain self-loops or multiple edges between nodes. The graph formed after adding edges should not contain self-loops or multiple edges.
• It is guaranteed that in the given graph, no two special employees are connected to each other. Function Description Complete the function getMaximumEdges in the editor. getMaximumEdges has the following parameters:
• int employee_nodes: the number of employees
• int employee_from[employee_edges]: the one end of the connection
• int employee_to[employee_edges]: the other end of the connection
• int special_employees[k]: the special employees
• int max_connections: the maximum number of special employees to which an employee can be connected Returns long: the maximum number of edges that can be added to the graph such that any employee is connected to at most max_connections number of special employees

Constraints

• 1 ≤ employee_nodes ≤ 2 * 10⁵
• 0 ≤ employee_edges ≤ min(2 * 10⁵, employee_nodes * (employee_nodes - 1) / 2)
• 1 ≤ max_connections ≤ k ≤ employee_nodes
• 1 ≤ employee_from[i], employee_to[i] ≤ employee_nodes
• 1 ≤ special_employees[i] ≤ employee_nodes

Example 1

Input:

employee_nodes = 4
employee_from = [1]
employee_to = [2]
special_employees = [1, 3]
max_connections = 1

Output:

2

Explanation: It is given that employee_nodes = 4, employee_edges = 1, k = 2, max_connections = 1, special_employees = [1, 3], employee_from = [1], and employee_to = [2]. Disjoint graph with 4 nodes numbered 1 to 4. Node 1 and 2 are connected through a bidirectional edge. Employees 1 and 3 are special, and max_connections = 1, so they cannot be connected. Hence, employee 4 can be connected to 1 and 2, making two total edges. Hence, the answer is 2.

Example 2

Input:

employee_nodes = 5
employee_from = [1, 2, 1]
employee_to = [2, 3, 3]
special_employees = [1, 4, 5]
max_connections = 3

Output:

7

Explanation: As max_connections = k = 3, hence we can connect all the employees, thus forming a fully connected graph. Hence, the answer is 7.

There are n players. They have to collect m points. All the players and coins are in 1-D space i.e. on a number line. The initial location of all the players is given as the array players where players[i] denotes the location of the ith player. The location of all the points is given as another array points where points[i] denotes the location of the ith point. In one second a player can either move 1 step left or 1 step right or not move at all. A point is considered collected if any of the n players had visited the point's location. The players can move simultaneously and independently of each other every second. The task is to find the minimum time (in seconds) required to collect all the points if players act optimally. Note: Locations of players and points are not necessarily given in sorted order. Function Description Complete the function getMinimumTime in the editor below. The function must return an integer; the minimum time required to collect all the points getMinimumTime has the following parameters:

• players[players[0]...players[n-1]]: an array of integers denoting the locations of players
• points[points[0]...points[m-1]]: an array of integers denoting the locations of points

Constraints

• 1 ≤ n, m ≤ 10⁵
• 1 ≤ players[i], points[i] ≤ 10⁹

Implement a prototype service for malware spread control in a network. There are g_nodes servers in a network and g_edges connections between its nodes. The bi-directional connection connects g_from[i] and g_to[i]. Some of the nodes are infected with malware. They are listed in a binary array, where if malware[i] = 1 node i is infected, and if malware[i] = 0, node i is not infected. Any infected node infects other non-infected nodes, which are directly connected. This process goes on until no new infections are possible. Exactly 1 node can be removed from the network. Return the index of the node to remove such that the total infected nodes in the remaining network are minimized. If multiple nodes lead to the same minimum result, then return the one with the lowest index. Function Description Complete the function getNodeToRemove in the editor. getNodeToRemove has the following parameter(s):

• int g_nodes: the number of nodes
• int g_from[n]: one end of the connections
• int g_to[n]: the other end of the connections
• int malware[n]: the affected nodes Returns int: the optimal node to remove

Constraints

• 1 ≤ g_nodes ≤ 10³
• 0 ≤ g_edges ≤ min(g_nodes*(g_nodes-1)/2, 10³)
• 1 ≤ g_from[i], g_to[i] ≤ n
• malware[i] = 0 or 1

Example 1

Input:

g_nodes = 9
g_from = [1, 2, 4, 6, 7]
g_to = [2, 3, 5, 7, 8]
malware = [0, 0, 1, 0, 1, 0, 0, 0, 0]

Output:

3

Explanation: Initially, nodes [3, 5] are infected. At the end, nodes [1, 2, 3, 4, 5] will be infected. If node 3 is removed, only nodes 4 and 5 are infected, which is the minimum possible. Return 3, the node to remove.

Example 2

Input:

g_nodes = 5
g_from = [1, 2, 3, 4]
g_to = [2, 3, 4, 5]
malware = [1, 1, 1, 1, 1]

Output:

1

Explanation: All nodes are infected even after removing any node. Return the lowest index, 1, as the answer.

Given a 4 x 4 matrix mat, the initial energy is 100. The task is to reach the last row of the matrix with the maximum possible energy left. The matrix can be traversed in the following way: Start with any cell in the first row.

• In each move, traverse from cell (i, j) of the ith row and jth column to any existing cell out of (i + 1, j - 1), (i + 1, j), or (i + 1, j + 1).
• Finish the traversal in the last row. After stepping on a cell (i, j), energy decreases by mat[i][j] units. Find the maximum possible energy left at the end of the traversal. Note: The final energy can be negative. Function Description Complete the function maxEnergy in the editor below. maxEnergy has the following parameter:
• int mat[4][4]: a matrix of integers Returns int: the maximum possible energy at the end of the traversal

Constraints

0 ≤ mat[i][j] < 100

Example 1

Input:

mat = [[10, 20, 30, 40], [60, 50, 20, 80], [10, 10, 10, 10], [60, 50, 60, 50]]

Output:

0

Explanation: Possible paths (0-based indexing is used):

• (0, 0) - (1, 1) - (2, 2) - (3, 3)
• (0, 1) - (1, 2) - (2, 2) - (3, 2) For the first path, energy left = 100 - 10 - 50 - 10 - 50 = -20 For the second path, energy left = 100 - 20 - 20 - 10 - 50 = 0 It can be proven that 0 is the maximum energy possible at the end of the traversal so return 0.

In a park, there are n friends standing in a random order, and they plan to throw a ball around. Each friend has a unique number in the range of 1 to n, inclusive. The i^th friend will always throw the ball towards the friend given at receiver[i], and this will happen each second. Friend 1 always starts with the ball, and a player always throws to another player. Determine which friend has the ball after k seconds pass. Note: Friends are numbered starting with 1. Function Description Complete the function throwTheBall in the editor. throwTheBall has the following parameters:

• int receiver[n]: the i^th friend will throw the ball to the friend indicated in receiver[i]
• int seconds: the time in seconds that the game lasts Returns int: the friend holding the ball at time = seconds

Constraints

• 2 ≤ n ≤ 10⁵
• 1 ≤ receiver[i] ≤ n (receiver[i] ≠ i)
• 1 ≤ seconds ≤ 10¹²

Example 1

Input:

receiver = [2, 4, 1, 5, 3]
seconds = 6

Output:

2

Explanation: After 6 seconds, the ball will be with friend 2.