题解

题面描述

给定一个仅由字符 $0$ 和 $1$ 组成的字符串 $s$ 和一个正整数 $n$。进行 $n$ 轮操作，每一轮按照如下规则构造一个新字符串 $t$：

• 新建一个空字符串 $t$；
• 对于原字符串 $s$ 中的第 $i$ 个字符 $s_i$：
  • 如果 $s_i$ 等于 $1$，则在 $t$ 的末尾插入字符串 "01"；
  • 如果 $s_i$ 等于 $0$，则在 $t$ 的末尾插入字符 "1"；
• 操作结束后，用字符串 $t$ 替换 $s$。

要求输出经过 $n$ 轮操作后字符串 $s$ 的长度，并且结果对模数 $10^9+7$ 取模。

思路分析

1. 操作规则分析

   对于任一轮操作，观察字符串中每个字符的转换规则：

   • 每个字符 $0$ 转换后变为字符串 "1"，长度为 $1$。
   • 每个字符 $1$ 转换后变为字符串 "01"，长度为 $2$。

   设在某轮中字符串 $s$ 的总长度为 $\ell$，其中字符 $1$ 的个数为 $b$，字符 $0$ 的个数为 $\ell - b$。则经过一次操作，新字符串 $t$ 的长度 $\ell'$ 为
   $\ell' = (\ell-b) \times 1 + b \times 2 = \ell + b.$

2. 状态转移和计数关系

   需要跟踪字符串长度 $\ell$ 和其中 $1$ 的个数。设：

   • $\ell_n$ 为第 $n$ 轮操作后字符串的长度。
   • $a_n$ 为其中 $0$ 的个数。
   • $b_n$ 为其中 $1$ 的个数。

   根据转换规则：

   • 字符 $0$ 转换为 "1"（产生 $0$ 个 $0$，$1$ 个 $1$）。
   • 字符 $1$ 转换为 "01"（产生 $1$ 个 $0$，$1$ 个 $1$）。

   因此状态转移有：

   $$a_{n+1} = b_n,\quad b_{n+1} = a_n + b_n = \ell_n.$$

   所以

   $$\ell_{n+1} = a_{n+1} + b_{n+1} = b_n + \ell_n.$$

   由观察可知 $b_n$ 恰好等于上一轮的字符串长度 $\ell_{n-1}$，从而得到递推关系：

   $$\ell_{n+1} = \ell_n + \ell_{n-1}.$$

   该递推关系与斐波那契数列非常相似，只不过初始值不同。

3. 初始条件

   设原始字符串 $s$ 的长度为 $\ell_0$，其中 $1$ 的个数为 $b_0$。那么：

   • $\ell_0 = |s|$
   • 第一轮操作后，$\ell_1 = |s| + b_0$

4. 求解过程

   对于 $n\ge1$，递推关系：

   $$\ell_n = \ell_{n-1} + \ell_{n-2}.$$

   可利用斐波那契数列的性质证明，对于 $n\ge1$ 有：

   $$\ell_n = \ell_1\cdot f_{n} + \ell_0\cdot f_{n-1},$$

   其中 $f_n$ 为标准斐波那契数（定义为 $f_0 = 0,\ f_1=1,\ f_n=f_{n-1}+f_{n-2}$）。

   利用快速倍增算法（或矩阵快速幂）可以在 $O(\log n)$ 的时间内求出 $f_n$ 和 $f_{n-1}$。

5. 取模运算

   因为 $n$ 的范围很大（最高 $10^{18}$），且最终答案可能非常大，所以所有计算均需要模 $10^9+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$个字符 $s_i$，如果$s_i$≡‘$1$’，在字符串$t$结尾插入字符串"$01$";反之，如果$s_i$=‘$0$’，在字符串$t$结尾插入字符‘$1$’。

• 将字符串$t$赋值给$s$，结束本轮。

求解，经过$n$ 轮操作后，字符串$s$的长度。由于答案可能很大，请将答案对$(10^9+7)$取模后输出。

输入描述

每个测试文件均包含多组测试数据。

第一行输入一个整数$T (1≦T≦10^5)$代表数据组数，每组测试数据描还如下:

在一行上输入一个长度为$1≦ len(s) ≤10^5$，仅由字符‘$0$’和‘$1$’组成的字符串 $s$。随后，输入一个整数$n(1≦n≦10^{18})$代表操作轮数。

除此之外，保证单个测试文件的$n$ 之和不超过$3×10^5$。

输出描述

对于每一组测试数据，新起一行。输出一个整数，代表经过$n$轮操作后，字符串$s$的长度。由于答案可能很大，请将答案对$(10^9+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$。