题解 | #分割序列#

题目链接

分割序列

题目描述

给定一个长度为 $N$ 的 01 字符串 $S$ ，你需要把它完全切分成若干连续子串，要求每个切分后的子串都恰好包含一个 '1'。求满足此要求的切分方案总数，结果对 $1,000,000,007$ 取模。

解题思路

本题的核心约束是每个切分后的子串必须恰好包含一个 '1'。这为我们提供了解决问题的关键切入点。

问题分析

由于每个子串必须有且仅有一个 '1'，这意味着字符串中的每一个 '1' 都必须属于一个不同的子串。因此，切分操作必然发生在两个连续的 '1' 之间。
例如，对于字符串 ...010010...，第一个 '1' 标志着它所在子串的结束（或核心部分），而第二个 '1' 标志着下一个子串的开始。切分必须在它们之间的 00 中进行。

乘法原理

在不同对的连续 '1' 之间如何切分是相互独立的决定。例如，在 101001 中，如何在第一个 101 部分切分，与如何在第二个 1001 部分切分无关。
因此，根据乘法原理，总的切分方案数等于在每个“1...1”片段之间进行切分的方案数的乘积。

子问题求解

我们的问题被分解为一系列独立的子问题：对于两个在索引 $i$ 和 $j$ （ $i < j$ ）的连续的 '1'，有多少种切分方法？
考虑这样一个片段，它以一个 '1' 开始，后跟若干个 '0'，直到下一个 '1' 出现。例如 100（下一个'1'在后面）。我们可以在 1 之后、第一个 0 之后、或第二个 0 之后进行切分。
- 切分成 1 | 00...
- 切分成 10 | 0...
- 切分成 100 | ...
如果两个连续的 '1' 的索引分别是 $i$ 和 $j$ ，它们之间的距离为 $d = j - i$ 。这表示从第一个 '1' 开始，共有 $d$ 个字符（包括第一个'1'，不包括第二个'1'）可以作为第一个子串的结尾。因此，就有 $d$ 种切分方案。

算法流程

遍历字符串，记录下所有 '1' 的位置索引。
处理边界情况：
- 如果没有 '1'，则无法满足条件，方案数为 0。
- 如果只有一个 '1'，则唯一的方案就是将整个字符串作为单个子串，方案数为 1。
如果有多个 '1'，则初始化方案数 $ans = 1$ 。
遍历相邻的 '1' 的索引对 $(i, j)$ ，将它们的距离 $(j-i)$ 累乘到 $ans$ 中，每次累乘后取模。

代码

c++
java
python

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    string s;
    cin >> s;
    
    vector<int> one_indices;
    for (int i = 0; i < n; ++i) {
        if (s[i] == '1') {
            one_indices.push_back(i);
        }
    }
    
    if (one_indices.empty()) {
        cout << 0 << endl;
        return 0;
    }
    
    long long ans = 1;
    long long mod = 1000000007;
    
    for (size_t i = 0; i < one_indices.size() - 1; ++i) {
        long long dist = one_indices[i + 1] - one_indices[i];
        ans = (ans * dist) % mod;
    }
    
    cout << ans << endl;
    
    return 0;
}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();
        
        List<Integer> one_indices = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '1') {
                one_indices.add(i);
            }
        }
        
        if (one_indices.isEmpty()) {
            System.out.println(0);
            return;
        }
        
        long ans = 1;
        long mod = 1000000007;
        
        for (int i = 0; i < one_indices.size() - 1; i++) {
            long dist = one_indices.get(i + 1) - one_indices.get(i);
            ans = (ans * dist) % mod;
        }
        
        System.out.println(ans);
    }
}

n = int(input())
s = input()

one_indices = [i for i, char in enumerate(s) if char == '1']

if not one_indices:
    print(0)
else:
    ans = 1
    mod = 1000000007
    
    for i in range(len(one_indices) - 1):
        dist = one_indices[i+1] - one_indices[i]
        ans = (ans * dist) % mod
        
    print(ans)

算法及复杂度

算法：思维、乘法原理
时间复杂度：需要遍历一次字符串来找到所有 '1' 的位置，时间复杂度为 $\mathcal{O}(N)$ 。然后遍历 '1' 的位置列表，最多有 $N$ 个 '1'，复杂度也为 $\mathcal{O}(N)$ 。因此，总时间复杂度为 $\mathcal{O}(N)$ 。
空间复杂度：需要一个列表来存储所有 '1' 的位置，最坏情况下字符串全是 '1'，列表长度为 $N$ 。因此，空间复杂度为 $\mathcal{O}(N)$ 。