Tap here to switch tabs
Problem
Submissions

Problem: Count Ways To Build Good Strings

Count Ways To Build Good Strings asks how many distinct strings can be formed by appending fixed runs of zeros or ones, with lengths between the given bounds. Return the count modulo a large prime.

Statement

Given integers low, high, zero, and one, you can construct a string starting from an empty string by repeatedly applying one of the following operations:

  • Append the character '0' written zero times.

  • Append the character '1' written one times.

A string is considered good if its length is between low and high inclusive.

Return the total number of different good strings that can be formed. Since the answer can be large, return it modulo 109+710^9 + 7.

Constraints:

  • 1≤1 \le low ≤\le high ≤105\le 10^5

  • 1≤1 \le zero, one ≤\le low

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Count Ways To Build Good Strings

Count Ways To Build Good Strings asks how many distinct strings can be formed by appending fixed runs of zeros or ones, with lengths between the given bounds. Return the count modulo a large prime.

Statement

Given integers low, high, zero, and one, you can construct a string starting from an empty string by repeatedly applying one of the following operations:

  • Append the character '0' written zero times.

  • Append the character '1' written one times.

A string is considered good if its length is between low and high inclusive.

Return the total number of different good strings that can be formed. Since the answer can be large, return it modulo 109+710^9 + 7.

Constraints:

  • 1≤1 \le low ≤\le high ≤105\le 10^5

  • 1≤1 \le zero, one ≤\le low