统计构造好字符串的方案数 图解题解

不写出具体的串，这题到底在数什么

从空串出发，每步末尾接 zero 个 0 或 one 个 1，步数随意；最后长度落在 low 到 high 里就算好字符串。方案数极大，只要对 10 的 9 次方加 7 取模（除以它留余数）。第一个例子 zero=one=1，长度须正好 3，长度 3 的 01 串都能拼，共 2 的 3 次方等于 8 个。

把每条构造路径都走一遍，为什么走不完

high 最大 10 的 5 次方，一条串可接几万步，每步在「接 0 块还是 1 块」里二选一，路径数翻成 2 的几万次方量级，根本列不出。而大量路径后半截一样：只要拼到同一长度，往后怎么接只由「还差多少」决定，跟前面接了什么无关，相同后续被从头重算。

串的内容都不看，只记长度为什么不丢方案

两条不同的构造顺序，接出的串必然不同：串里每段连续 0、连续 1 都只能拆成整块 zero 个 0、one 个 1，拆法唯一，从串能反推怎么接出来。所以数不同的好字符串就等于数不同的构造顺序。

既然后续只看当前长度，就用动态规划（把「拼出长度 len 有几种接法」的小问题算好存表，长的查短的）：定义 dp[len] 为恰好拼出长度 len 的方案数。起点 dp[0]=1，空串什么都不接、算一种，是累加的种子。

最后一块是 0 还是 1，两条来路为什么加起来就是全部

盯住拼到长度 len 的顺序的最后一步，即转移（由更短长度的已知答案推出当前格）：最后接的要么是 zero 个 0，去掉剩拼到 len-zero 的顺序；要么是 one 个 1，剩拼到 len-one 的。按最后一块分两堆，不重叠也无第三种结尾，所以 dp[len]=dp[len-zero]+dp[len-one]。下标减成负数说明退不回去，按 0 跳过。

答案不是 dp[high] 一格，low 到 high 里每格都算好串，要把 dp[low] 一路加到 dp[high]，每加一步都取模。

zero=1、one=2 的示例，5 是怎么加出来的

拿第二个例子 low=2、high=3、zero=1、one=2 填表。dp[0]=1。长度 1：退 1 步落在 dp[0]=1，退 2 步负下标不算，dp[1]=1，对应 0。长度 2：dp[1]+dp[0]=1+1=2，对应 00 和 11。长度 3：dp[2]+dp[1]=2+1=3，对应 000、011、110。长度 2、3 都在区间，答案 dp[2]+dp[3]=2+3=5，正是题面输出的 5。

dp[0] 记成 0，整张表为什么会一路塌成 0

dp[0] 是全表唯一凭空给定的，其余每格都由它加出来，记成 0 就全表塌成 0，答案归零——空串必须算一种。长度从 1 推到 high，每格看两条来路，时间 O(high)（随 high 线性增长的记法）；dp 数组开 high+1 格，空间 O(high)。

两条来路全断的格子记 0 正常，不是算错。求和两端都要取到，low 等于 high 时区间只剩一格，写成开区间就漏了。取模别攒到最后：两格相加就可能冲破 32 位，C++、Java 用 long 承接再取模，Python 大整数不溢出，但仍要按题意取模。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
        mod = 10**9 + 7
        dp = [0] * (high + 1)
        dp[0] = 1
        ans = 0
        for i in range(1, high + 1):
            if i >= zero:
                dp[i] += dp[i - zero]
            if i >= one:
                dp[i] += dp[i - one]
            dp[i] %= mod
            if i >= low:
                ans = (ans + dp[i]) % mod
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    const int mod = 1e9 + 7;

    int countGoodStrings(int low, int high, int zero, int one) {
        vector<int> dp(high + 1, 0);
        dp[0] = 1;
        long ans = 0;
        for (int i = 1; i <= high; i++) {
            long cur = 0;
            if (i >= zero) cur += dp[i - zero];
            if (i >= one) cur += dp[i - one];
            dp[i] = cur % mod;
            if (i >= low) ans = (ans + dp[i]) % mod;
        }
        return (int) ans;
    }
};

Java

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private static final int MOD = (int) 1e9 + 7;

    public int countGoodStrings(int low, int high, int zero, int one) {
        int[] dp = new int[high + 1];
        dp[0] = 1;
        long ans = 0;
        for (int i = 1; i <= high; i++) {
            long cur = 0;
            if (i >= zero) {
                cur += dp[i - zero];
            }
            if (i >= one) {
                cur += dp[i - one];
            }
            dp[i] = (int) (cur % MOD);
            if (i >= low) {
                ans = (ans + dp[i]) % MOD;
            }
        }
        return (int) ans;
    }
}