#P2805. 第3题-字符串
          
                        
                                    
                      
        
              - 
          
          
                      1000ms
            
          
                      Tried: 32
            Accepted: 7
            Difficulty: 5
            
          
          
          
                       所属公司 : 
                              阿里
                                
            
                        
              时间 :2025年4月8日-阿里淘天(算法岗)
                              
                      
          
 
- 
                        算法标签>动态规划          
 
第3题-字符串
题解
题面描述
给定一个仅由字符 0 和 1 组成的字符串 s 和一个正整数 n。进行 n 轮操作,每一轮按照如下规则构造一个新字符串 t:
- 新建一个空字符串 t;
 - 对于原字符串 s 中的第 i 个字符 si:
- 如果 si 等于 1,则在 t 的末尾插入字符串 "01";
 - 如果 si 等于 0,则在 t 的末尾插入字符 "1";
 
 - 操作结束后,用字符串 t 替换 s。
 
要求输出经过 n 轮操作后字符串 s 的长度,并且结果对模数 109+7 取模。
思路分析
- 
操作规则分析
对于任一轮操作,观察字符串中每个字符的转换规则:
- 每个字符 0 转换后变为字符串 "1",长度为 1。
 - 每个字符 1 转换后变为字符串 "01",长度为 2。
 
设在某轮中字符串 s 的总长度为 ℓ,其中字符 1 的个数为 b,字符 0 的个数为 ℓ−b。则经过一次操作,新字符串 t 的长度 ℓ′ 为
ℓ′=(ℓ−b)×1+b×2=ℓ+b. - 
状态转移和计数关系
需要跟踪字符串长度 ℓ 和其中 1 的个数。设:
- ℓn 为第 n 轮操作后字符串的长度。
 - an 为其中 0 的个数。
 - bn 为其中 1 的个数。
 
根据转换规则:
- 字符 0 转换为 "1"(产生 0 个 0,1 个 1)。
 - 字符 1 转换为 "01"(产生 1 个 0,1 个 1)。
 
因此状态转移有:
an+1=bn,bn+1=an+bn=ℓn.所以
ℓn+1=an+1+bn+1=bn+ℓn.由观察可知 bn 恰好等于上一轮的字符串长度 ℓn−1,从而得到递推关系:
ℓn+1=ℓn+ℓn−1.该递推关系与斐波那契数列非常相似,只不过初始值不同。
 - 
初始条件
设原始字符串 s 的长度为 ℓ0,其中 1 的个数为 b0。那么:
- ℓ0=∣s∣
 - 第一轮操作后,ℓ1=∣s∣+b0
 
 - 
求解过程
对于 n≥1,递推关系:
ℓn=ℓn−1+ℓn−2.可利用斐波那契数列的性质证明,对于 n≥1 有:
ℓn=ℓ1⋅fn+ℓ0⋅fn−1,其中 fn 为标准斐波那契数(定义为 f0=0, f1=1, fn=fn−1+fn−2)。
利用快速倍增算法(或矩阵快速幂)可以在 O(logn) 的时间内求出 fn 和 fn−1。
 - 
取模运算
因为 n 的范围很大(最高 1018),且最终答案可能非常大,所以所有计算均需要模 109+7 处理。
 
C++
#include <iostream>
#include <string>
using namespace std;
// 定义模数 MOD = 10^9+7
const long long MOD = 1000000007;
// 快速倍增算法求斐波那契数
// 函数返回 pair(f_n, f_(n+1)),其中 f_n 表示第 n 个斐波那契数
pair<long long, long long> fastFib(long long n) {
    if (n == 0) return {0, 1}; // 基础情况:f_0 = 0, f_1 = 1
    auto p = fastFib(n >> 1); // 递归计算 f_(floor(n/2)) 和 f_(floor(n/2)+1)
    long long a = p.first, b = p.second;
    // 计算 f_(2k) = f_k * (2 * f_(k+1) - f_k)
    long long c = (a * ((2 * b % MOD + MOD - a) % MOD)) % MOD;
    // 计算 f_(2k+1) = f_k^2 + f_(k+1)^2
    long long d = ((a * a) % MOD + (b * b) % MOD) % MOD;
    if (n & 1)
        return {d, (c + d) % MOD};
    else
        return {c, d};
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int T; // 读取数据组数 T
    cin >> T;
    while (T--) {
        string s;
        long long n;
        cin >> s >> n;
 
        // len0 表示初始字符串长度 |s|
        long long len0 = s.size();
        // 统计原始字符串中字符 '1' 的个数 b0
        long long count1 = 0;
        for (char c : s) {
            if (c == '1') count1++;
        }
 
        // len1 = |s| + (串中 1 的个数)
        long long len1 = len0 + count1;
 
        // 如果 n 为 0,则直接输出初始字符串长度(题目中 n >= 1,这里作为防御处理)
        if (n == 0) {
            cout << len0 % MOD << "\n";
            continue;
        }
 
        // 利用公式:len_n = len1 * f_n + len0 * f_(n-1) (模 MOD)
        // 使用快速倍增算法求出 f_n 和 f_(n+1)
        auto fibPair = fastFib(n);
        long long fn = fibPair.first;      // 得到 f_n
        long long fn_plus = fibPair.second;  // 得到 f_(n+1)
 
        // 根据 f_(n+1) = f_n + f_(n-1),计算 f_(n-1) = f_(n+1) - f_n
        long long fn_minus = (fn_plus + MOD - fn) % MOD;
 
        // 当 n = 1 时,答案就是 len1
        if (n == 1) {
            cout << len1 % MOD << "\n";
        } else {
            long long ans = ((len1 % MOD) * fn % MOD + (len0 % MOD) * fn_minus % MOD) % MOD;
            cout << ans % MOD << "\n";
        }
    }
    return 0;
}
Python
MOD = 10**9 + 7
# 快速倍增算法,返回 (f_n, f_(n+1))
def fast_fib(n):
    if n == 0:
        return (0, 1)  # 基础情况:f_0 = 0, f_1 = 1
    a, b = fast_fib(n >> 1)  # 递归计算 f_(floor(n/2)) 和 f_(floor(n/2)+1)
    # 计算 f_(2k) = f_k * (2 * f_(k+1) - f_k)
    c = (a * ((2 * b - a) % MOD)) % MOD
    # 计算 f_(2k+1) = f_k^2 + f_(k+1)^2
    d = (a * a + b * b) % MOD
    if n & 1:
        return (d, (c + d) % MOD)
    else:
        return (c, d)
    
import sys
input_data = sys.stdin.read().split()
t = int(input_data[0])
index = 1
res = []
for _ in range(t):
    s = input_data[index]
    n = int(input_data[index+1])
    index += 2
    
    # len0 为初始字符串长度 |s|
    len0 = len(s)
    # 计算字符串中字符 '1' 的个数 b0
    count1 = s.count('1')
    # len1 = |s| + (串中 1 的个数)
    len1 = len0 + count1
    
    # n == 0 时直接输出初始长度(题中 n >= 1,这里作为防御性处理)
    if n == 0:
        res.append(str(len0 % MOD))
        continue
    
    # 公式:len_n = len1 * f_n + len0 * f_(n-1) (模 MOD)
    fn, fn_plus = fast_fib(n)  # 得到 f_n 和 f_(n+1)
    # 根据 f_(n+1) = f_n + f_(n-1) 得 f_(n-1) = f_(n+1) - f_n
    fn_minus = (fn_plus - fn) % MOD
    
    if n == 1:
        ans = len1 % MOD
    else:
        ans = (len1 % MOD * fn % MOD + len0 % MOD * fn_minus % MOD) % MOD
    res.append(str(ans))
print("\n".join(res))
Java
import java.io.*;
import java.util.*;
public class Main {
    // 定义模数 MOD = 10^9+7
    static final long MOD = 1000000007;
    
    // 快速倍增算法,返回一个数组 {f_n, f_(n+1)}
    public static long[] fastFib(long n) {
        if (n == 0) return new long[]{0, 1}; // 基础情况:f_0 = 0, f_1 = 1
        long[] p = fastFib(n >> 1); // 递归计算 f_(floor(n/2)) 和 f_(floor(n/2)+1)
        long a = p[0], b = p[1];
        // 计算 f_(2k) = f_k * (2 * f_(k+1) - f_k)
        long c = (a * ((2 * b % MOD + MOD - a) % MOD)) % MOD;
        // 计算 f_(2k+1) = f_k^2 + f_(k+1)^2
        long d = ((a * a) % MOD + (b * b) % MOD) % MOD;
        if ((n & 1) == 1)
            return new long[]{d, (c + d) % MOD};
        else
            return new long[]{c, d};
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 读取数据组数 T
        int T = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            String[] parts = br.readLine().split(" ");
            String s = parts[0];
            long n = Long.parseLong(parts[1]);
            
            // len0 表示初始字符串长度 |s|
            long len0 = s.length();
            // 计算字符串中字符 '1' 的个数 b0
            long count1 = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '1')
                    count1++;
            }
            // len1 = |s| + (串中 1 的个数)
            long len1 = len0 + count1;
            
            // 当 n 为 0 时,直接输出初始长度(这里作为防御性处理,题中 n >= 1)
            if (n == 0) {
                sb.append(len0 % MOD).append("\n");
                continue;
            }
            
            // 利用公式:len_n = len1 * f_n + len0 * f_(n-1) 模 MOD
            // 快速倍增算法得到 {f_n, f_(n+1)}
            long[] fibPair = fastFib(n);
            long fn = fibPair[0];      // f_n
            long fn_plus = fibPair[1]; // f_(n+1)
            // 根据 f_(n+1) = f_n + f_(n-1),计算 f_(n-1) = f_(n+1) - f_n
            long fn_minus = (fn_plus + MOD - fn) % MOD;
            
            long ans;
            if (n == 1) {
                ans = len1 % MOD;
            } else {
                ans = ((len1 % MOD) * fn % MOD + (len0 % MOD) * fn_minus % MOD) % MOD;
            }
            sb.append(ans).append("\n");
        }
        System.out.print(sb.toString());
    }
}
        题目内容
对于给定的仅由字符‘0’和‘1’组成的字符串s,按照下方规则进行n 轮操作,每一轮:
- 
新建一个为空的辅助字符串t;
 - 
对于第i个字符 si,如果si≡‘1’,在字符串t结尾插入字符串"01";反之,如果si=‘0’,在字符串t结尾插入字符‘1’。
 - 
将字符串t赋值给s,结束本轮。
 
求解,经过n 轮操作后,字符串s的长度。由于答案可能很大,请将答案对(109+7)取模后输出。
输入描述
每个测试文件均包含多组测试数据。
第一行输入一个整数T(1≦T≦105)代表数据组数,每组测试数据描还如下:
在一行上输入一个长度为1≦len(s)≤105,仅由字符‘0’和‘1’组成的字符串 s。随后,输入一个整数n(1≦n≦1018)代表操作轮数。
除此之外,保证单个测试文件的n 之和不超过3×105。
输出描述
对于每一组测试数据,新起一行。输出一个整数,代表经过n轮操作后,字符串s的长度。由于答案可能很大,请将答案对(109+7) 取模后输出。
样例1
输入
3
01 2
10101 1
101 10
输出
5 
8
377
说明
对于第一组测试数据:
- 
第一轮,字符串t="1 01"
 - 
第二轮,字符串t="01 1 01"
综上,结束时字符串s的长度为5。
 
对于第二组测试数据:
- 
第一轮,字符串t="01 1 01 1 01"
综上,结束时字符串s的长度为8。