Package g3101_3200.s3130_find_all_possible_stable_binary_arrays_ii

Class Solution

java.lang.Object
g3101_3200.s3130_find_all_possible_stable_binary_arrays_ii.Solution
public class Solution extends java.lang.Object
3130 - Find All Possible Stable Binary Arrays II.

Hard

You are given 3 positive integers zero, one, and limit.

A binary array arr is called stable if:

  • The number of occurrences of 0 in arr is exactly zero.
  • The number of occurrences of 1 in arr is exactly one.
  • Each subarray of arr with a size greater than limit must contain both 0 and 1.

Return the total number of stable binary arrays.

Since the answer may be very large, return it modulo 109 + 7.

Example 1:

Input: zero = 1, one = 1, limit = 2

Output: 2

Explanation:

The two possible stable binary arrays are [1,0] and [0,1].

Example 2:

Input: zero = 1, one = 2, limit = 1

Output: 1

Explanation:

The only possible stable binary array is [1,0,1].

Example 3:

Input: zero = 3, one = 3, limit = 2

Output: 14

Explanation:

All the possible stable binary arrays are [0,0,1,0,1,1], [0,0,1,1,0,1], [0,1,0,0,1,1], [0,1,0,1,0,1], [0,1,0,1,1,0], [0,1,1,0,0,1], [0,1,1,0,1,0], [1,0,0,1,0,1], [1,0,0,1,1,0], [1,0,1,0,0,1], [1,0,1,0,1,0], [1,0,1,1,0,0], [1,1,0,0,1,0], and [1,1,0,1,0,0].

Constraints:

  • 1 <= zero, one, limit <= 1000

  • Constructor Summary

    Constructors
    Constructor
    Description
    Solution()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    long
    comb(int n, int k)
     
    long
    getInverse(long n, long mod)
     
    int
    numberOfStableArrays(int zero, int one, int limit)
     
    long
    quickPower(long base, long power, long p)
     

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • Solution

      public Solution()

  • Method Details

    • numberOfStableArrays

      public int numberOfStableArrays(int zero, int one, int limit)

    • comb

      public long comb(int n, int k)

    • getInverse

      public long getInverse(long n, long mod)

    • quickPower

      public long quickPower(long base, long power, long p)