题解
题面描述
在一个文本处理系统中，字符被分为两类：普通字符（小写字母）和活跃字符（大写字母）。系统支持一种“增殖”操作：每次操作时，字符串中的每个活跃字符都会自我复制，即由一个活跃字符变为两个连续且相同的活跃字符；而所有普通字符保持不变。
给定一个初始字符串 s 和操作次数 k，请你计算执行 k 次增殖操作后，字符串的长度。由于长度可能极大，请将结果对 109+7 取模后输出。
输入描述：
- 第一行包含一个由大小写字母组成的字符串 s，长度不超过 106，表示初始字符串。
- 第二行包含一个整数 k，表示增殖操作的次数，满足 0≤k≤109。
输出描述：
- 输出一个整数，表示执行 k 次增殖操作后字符串长度对 109+7 取模的结果。
思路分析
-
字符串变化的规律：
对于初始字符串 s，设其长度为 n，其中活跃字符（大写字母）的个数为 u。
每次增殖操作时，每个活跃字符都会被复制一次，也就是说会额外增加 1 个字符。
-
一次操作的结果：
- 字符串长度变为：
n+u
- 原来 u 个活跃字符经过复制后，变为 2u 个活跃字符。
-
多次操作的递推规律：
记第 i 次操作后活跃字符的个数为 ui，那么有
u0=u
u1=2u0=2u
u2=2u1=22u
…
ui=2iu
同时，每一次操作时，字符串长度增加的部分就是上一轮的活跃字符数。
因此第 k 次操作后，字符串总长度 Lk 为
Lk = n + ∑i=0k−1ui = n + u∑i=0k−12i
注意求和公式
∑i=0k−12i=2k−1
则有
Lk=n+u(2k−1)
-
取模运算：
最后答案需要对 109+7 取模，因此最终结果为
ans=(n+u(2k−1))mod(109+7)
在实际代码中，计算 2kmod(109+7) 时需要使用快速幂（模幂运算）。
代码实现
MOD = 10**9 + 7 # 定义模数10^9+7
def mod_exp(base, exponent, mod):
result = 1
base %= mod
while exponent > 0:
if exponent % 2 == 1:
result = (result * base) % mod
base = (base * base) % mod
exponent //= 2
return result
def main():
s = input().strip()
k = int(input().strip())
n = len(s)
u = sum(1 for c in s if 'A' <= c <= 'Z')
if k == 0:
print(n % MOD)
return
# 正确调用：使用变量 k 作为指数
two_k = mod_exp(2, k, MOD)
ans = (n + u * ((two_k - 1) % MOD)) % MOD
print(ans)
if __name__ == "__main__":
main()
import java.util.Scanner;
public class Main {
// 定义模数10^9+7
static final long MOD = 1000000007;
public static long modExp(long base, long exponent, long mod) {
long result = 1;
base %= mod;
while (exponent > 0) {
// 如果当前指数为奇数，更新结果
if ((exponent & 1) == 1) {
result = (result * base) % mod;
}
base = (base * base) % mod; // 底数自乘
exponent >>= 1; // 指数右移1位
}
return result;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读入初始字符串s和操作次数k
String s = sc.next();
long k = sc.nextLong();
int n = s.length(); // 初始字符串长度n
int u = 0; // 初始活跃字符（大写字母）个数u
// 遍历字符串统计活跃字符
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c >= 'A' && c <= 'Z') {
u++;
}
}
// 当操作次数为0时，直接输出初始字符串长度
if (k == 0) {
System.out.println(n % MOD);
return;
}
// 计算2^k mod MOD
long twoK = modExp(2, k, MOD);
// 根据公式L_k = n + u(2^k - 1)得到最终字符串的长度
long ans = (n + u * ((twoK - 1 + MOD) % MOD)) % MOD;
System.out.println(ans);
}
}
