For a string word of length n consisting of lowercase English characters, it can be transformed as follows.
For each character of the string:
- If the character is 'z', it is replaced by "ab".
- Otherwise, it is replaced by its next higher character, for example, 'a' is replaced by 'b', 'b' by 'c' ... and 'y' by 'z'.
Thus, if the initial string is "azbk" it is "babcl" after 1 transformation.
As a fun trivia, HackerRank publishes a puzzle for all its employees each week. The goal for this week is to find the length of the resultant string after exactly
ttransformations are performed as described above. Since the answer can be large, find the answer taking modulo (10⁹ + 7).
Example 1
Input:
word = "abczy"
t = 2Output:
TO-DOExplanation:
Consider word = "abczy" and the number of transformations t = 2.
In the 1st transformation, the characters are transformed as follows:
- a → b
- b → c
- c → d
- z → ab
- y → z Resulting string: "bcdabz" In the 2nd transformation:
- b → c
- c → d
- d → e
- a → b
- b → c Resulting string: "cdedbc"
解法
考虑单个字符 c 经 t 步变换后的长度 f(c, t)。递推：'z' → 'a' + 'b'(一步后变成两个字符 a 和 b，长度 2)；其它 c → next(c)(长度 1)。设 L[c][t] 为字符 c 经 t 步后产生的字符串长度，状态可用每字母分别滚动；或观察：cnt[i][t] = "经过 t 步后第 i 个字母在结果中的个数"，转移：cnt[i][t] = cnt[i-1][t-1](i ≠ 'a','b')，cnt[0][t] = cnt[25][t-1](z→ab 贡献 a)，cnt[1][t] = cnt[0][t-1] + cnt[25][t-1](b 来自 a 和 z)。初始 cnt[i][0] = 字符串中字母 i 的个数。答案 = sum cnt[i][t] mod p。时间 O(26·t)。
MOD = 10 ** 9 + 7
def transformations_length(word: str, t: int) -> int:
cnt = [0] * 26
for c in word:
cnt[ord(c) - ord('a')] += 1
for _ in range(t):
nxt = [0] * 26
for i in range(25):
nxt[i + 1] = (nxt[i + 1] + cnt[i]) % MOD
# z -> a + b
nxt[0] = (nxt[0] + cnt[25]) % MOD
nxt[1] = (nxt[1] + cnt[25]) % MOD
cnt = nxt
return sum(cnt) % MODclass Solution {
static final int MOD = 1_000_000_007;
public int transformationsLength(String word, int t) {
long[] cnt = new long[26];
for (char c : word.toCharArray()) cnt[c - 'a']++;
for (int s = 0; s < t; s++) {
long[] nxt = new long[26];
for (int i = 0; i < 25; i++) nxt[i + 1] = (nxt[i + 1] + cnt[i]) % MOD;
nxt[0] = (nxt[0] + cnt[25]) % MOD;
nxt[1] = (nxt[1] + cnt[25]) % MOD;
cnt = nxt;
}
long s = 0; for (long v : cnt) s = (s + v) % MOD;
return (int) s;
}
}#include <bits/stdc++.h>
using namespace std;
class Solution {
static constexpr long long MOD = 1000000007;
public:
int transformationsLength(string word, int t) {
vector<long long> cnt(26, 0);
for (char c : word) cnt[c - 'a']++;
for (int s = 0; s < t; s++) {
vector<long long> nxt(26, 0);
for (int i = 0; i < 25; i++) nxt[i + 1] = (nxt[i + 1] + cnt[i]) % MOD;
nxt[0] = (nxt[0] + cnt[25]) % MOD;
nxt[1] = (nxt[1] + cnt[25]) % MOD;
cnt = nxt;
}
long long total = 0;
for (auto v : cnt) total = (total + v) % MOD;
return (int) total;
}
};In the context of training a machine learning model for data pattern detection and categorization, there is a dataset represented as an array of n integers, arr[i], where 1A subsequence of a given array can be defined as a sequence that results from removing elements from the array at any position without altering the relative order of the remaining elements. An empty subsequence contains no elements. The Minimum Excludant (MEX) of a sequence is the smallest non-negative integer that is absent from the sequence. The MEX of an empty subsequence is zero. **Function Description** Complete the function countSubsequencesin the editor.countSubsequences` has the following parameters:
List arr: an array of integersint l: the lower bound of the rangeint r: the upper bound of the range Returns int: the number of subsequences with MEX within the range[l, r], modulo(10⁹ + 7)
Constraints
1≤n≤3*10⁵0≤arr[i]≤10⁹0≤l≤r≤10⁹
Example 1
Input:
arr = [0, 1, 2]
l = 1
r = 2Output:
3Explanation: The Minimum Excludant (MEX) for all possible subsequences is demonstrated as follows:
- An empty subsequence ([]) has a MEX of 0.
- A subsequence ([0]) has a MEX of 1.
- A subsequence ([1]) has a MEX of 0.
- A subsequence ([2]) has a MEX of 0.
- For the subsequence ([0, 1]), the MEX is 2.
- In the case of ([0, 2]), the MEX is 1.
- In the case of ([1, 2]), the MEX is 0.
- Finally, when considering the subsequence [0,1,2], the MEX is 3, There are 2 subsequences with MEX of 1 and 1 subsequence with a MEX of 2. Hence, the answer is 1+2=3.
解法
设 f(k) = MEX 恰好 = k 的子序列数。MEX=k 等价于：子序列包含 0..k-1 中每个值至少一次，且不包含 k。设 c[v] = arr 中值为 v 的元素数。则 f(k) = ∏_{v=0}^{k-1}(2^{c[v]}-1) · 1^{c[k]} · 2^{(剩余元素数, 值 > k)}。注意"不包含 k"乘 1(不选这些位置)，"剩余值 > k 任意"乘 2^c[>k]。逐 k 累加 l ≤ k ≤ r 的 f(k) mod 1e9+7。时间 O(n + (r-l+1))。
from collections import Counter
from typing import List
MOD = 10 ** 9 + 7
def count_subsequences(arr: List[int], l: int, r: int) -> int:
n = len(arr)
cnt = Counter(arr)
max_v = max(r + 1, max(cnt) + 1 if cnt else 1)
# precompute powers of 2 mod
pow2 = [1] * (n + 1)
for i in range(1, n + 1):
pow2[i] = pow2[i - 1] * 2 % MOD
# prefix product of (2^c[v]-1) for v=0..k-1
# and count of elements with value >= k
total = 0
prefix_prod = 1
elements_with_value_gt_k = sum(cnt[v] for v in cnt if v > 0) # elements with v > 0
# Use total - cumulative cnt[0..k]
cum_le_k = 0
for k in range(0, max_v + 1):
# at this point: prefix_prod = ∏_{v=0}^{k-1}(2^c[v]-1)
# elements with value > k = n - cum_le_k - cnt[k]
c_k = cnt.get(k, 0)
rest = n - cum_le_k - c_k
# subseq with MEX = k: prefix_prod * 1 (none of k) * 2^rest (any subset of v > k)
if l <= k <= r:
total = (total + prefix_prod * pow2[rest]) % MOD
# advance: include v = k now
prefix_prod = prefix_prod * ((pow2[c_k] - 1) % MOD) % MOD
cum_le_k += c_k
if prefix_prod == 0 and k >= r:
break
return totalimport java.util.*;
class Solution {
static final long MOD = 1_000_000_007L;
public int countSubsequences(List<Integer> arr, int l, int r) {
int n = arr.size();
Map<Integer, Integer> cnt = new HashMap<>();
for (int v : arr) cnt.merge(v, 1, Integer::sum);
int maxV = r + 1;
for (int v : cnt.keySet()) maxV = Math.max(maxV, v + 1);
long[] pow2 = new long[n + 1];
pow2[0] = 1;
for (int i = 1; i <= n; i++) pow2[i] = pow2[i - 1] * 2 % MOD;
long total = 0, prefixProd = 1;
int cumLeK = 0;
for (int k = 0; k <= maxV; k++) {
int cK = cnt.getOrDefault(k, 0);
int rest = n - cumLeK - cK;
if (l <= k && k <= r) total = (total + prefixProd * pow2[rest]) % MOD;
prefixProd = prefixProd * ((pow2[cK] - 1 + MOD) % MOD) % MOD;
cumLeK += cK;
if (prefixProd == 0 && k >= r) break;
}
return (int) total;
}
}#include <bits/stdc++.h>
using namespace std;
class Solution {
static constexpr long long MOD = 1000000007;
public:
int countSubsequences(vector<int>& arr, int l, int r) {
int n = arr.size();
unordered_map<int,int> cnt;
for (int v : arr) cnt[v]++;
int maxV = r + 1;
for (auto& [k, v] : cnt) maxV = max(maxV, k + 1);
vector<long long> pow2(n + 1, 1);
for (int i = 1; i <= n; i++) pow2[i] = pow2[i - 1] * 2 % MOD;
long long total = 0, prefixProd = 1;
int cumLeK = 0;
for (int k = 0; k <= maxV; k++) {
int cK = cnt.count(k) ? cnt[k] : 0;
int rest = n - cumLeK - cK;
if (k >= l && k <= r) total = (total + prefixProd * pow2[rest]) % MOD;
prefixProd = prefixProd * ((pow2[cK] - 1 + MOD) % MOD) % MOD;
cumLeK += cK;
if (prefixProd == 0 && k >= r) break;
}
return (int) total;
}
};There is a lottery with c coupons and p participants. Each participant picks exactly one coupon. Coupons are numbered from lowLimit to highLimit, inclusive. The winner of the lottery is any participant who owns a coupon with the sum of digits s written on it. If there is more than one winner, then the prize is split equally among them.
- Determine
sin such a way that there is at least one winner, and the prize is split among the most participants. - Also determine how many ways the required sum
scan be chosen, so that the lottery is split among the maximum number of participants. Function Description Complete the functionwaysToChooseSumin the editor below. The function must return an array of long integers with 2 elements: - The total number of ways to choose sum so that maximum possible participants win the lottery.
- The number of participants who will win the lottery.
waysToChooseSumhas the following parameter(s): long lowLimit: a long integer, the starting number of the lottery couponslong highLimit: a long integer, the ending number of the lottery coupons
Constraints
- 1 ≤
lowLimit<highLimit≤ 10¹⁸
解法
数位 DP：用数位 DP 计算"区间 [low, high] 内每个数字和 s 出现的次数" g[s]。g[s] = f(high, s) - f(low-1, s)，f 用 memo 化数位 DP(受限/tight 标记)。统计 max(g) 的值及 argmax 的个数。数字和上限 s ≤ 9·19 = 171。时间 O(19·171·10) per call。
from functools import lru_cache
from typing import List
def ways_to_choose_sum(low_limit: int, high_limit: int) -> List[int]:
def count_up_to(N: int) -> List[int]:
if N < 0:
return [0] * 200
digits = list(map(int, str(N)))
# cnt[i] = number of integers in [0, N] with digit sum == i
from functools import lru_cache
@lru_cache(maxsize=None)
def dp(pos: int, sm: int, tight: bool) -> tuple:
if pos == len(digits):
arr = [0] * 200
arr[sm] = 1
return tuple(arr)
limit = digits[pos] if tight else 9
total = [0] * 200
for d in range(0, limit + 1):
sub = dp(pos + 1, sm + d, tight and d == limit)
for i in range(200):
total[i] += sub[i]
return tuple(total)
return list(dp(0, 0, True))
g_high = count_up_to(high_limit)
g_lowm = count_up_to(low_limit - 1)
g = [a - b for a, b in zip(g_high, g_lowm)]
best = max(g)
ways = sum(1 for v in g if v == best)
return [ways, best]import java.util.*;
class Solution {
long[][][] memo; int[] dig;
long[] dp(int pos, int sm, int tight) {
if (pos == dig.length) { long[] a = new long[200]; a[sm] = 1; return a; }
if (memo[pos][sm][tight] != null) return memo[pos][sm][tight];
int limit = tight == 1 ? dig[pos] : 9;
long[] out = new long[200];
for (int d = 0; d <= limit; d++) {
long[] sub = dp(pos + 1, sm + d, (tight == 1 && d == limit) ? 1 : 0);
for (int i = 0; i < 200; i++) out[i] += sub[i];
}
memo[pos][sm][tight] = out;
return out;
}
long[] countUpTo(long N) {
if (N < 0) return new long[200];
dig = Long.toString(N).chars().map(c -> c - '0').toArray();
memo = new long[dig.length + 1][200][2][];
return dp(0, 0, 1);
}
public long[] waysToChooseSum(long lowLimit, long highLimit) {
long[] hi = countUpTo(highLimit);
long[] lo = countUpTo(lowLimit - 1);
long best = 0, ways = 0;
for (int i = 0; i < 200; i++) {
long d = hi[i] - lo[i];
if (d > best) { best = d; ways = 1; } else if (d == best && d > 0) ways++;
}
return new long[]{ways, best};
}
}#include <bits/stdc++.h>
using namespace std;
class Solution {
vector<int> dig;
map<tuple<int,int,int>, vector<long long>> memo;
vector<long long> dp(int pos, int sm, int tight) {
if (pos == (int)dig.size()) { vector<long long> a(200, 0); a[sm] = 1; return a; }
auto key = make_tuple(pos, sm, tight);
if (memo.count(key)) return memo[key];
int limit = tight ? dig[pos] : 9;
vector<long long> out(200, 0);
for (int d = 0; d <= limit; d++) {
auto sub = dp(pos + 1, sm + d, tight && d == limit);
for (int i = 0; i < 200; i++) out[i] += sub[i];
}
return memo[key] = out;
}
vector<long long> countUpTo(long long N) {
if (N < 0) return vector<long long>(200, 0);
dig.clear(); memo.clear();
for (char c : to_string(N)) dig.push_back(c - '0');
return dp(0, 0, 1);
}
public:
vector<long long> waysToChooseSum(long long lowLimit, long long highLimit) {
auto hi = countUpTo(highLimit);
auto lo = countUpTo(lowLimit - 1);
long long best = 0, ways = 0;
for (int i = 0; i < 200; i++) {
long long d = hi[i] - lo[i];
if (d > best) { best = d; ways = 1; } else if (d == best && d > 0) ways++;
}
return {ways, best};
}
};