Hello, Codeforces community!↵
↵
I recently faced an interesting problem during a company online assessment, and I wanted to share it with you all. Unfortunately, I couldn't solve it, and I’m reaching out for your help.↵
↵
**Problem Description**↵
↵
You are given three integers: A,B,C. Your task is to count the number of possible arrays of size A that satisfy the following conditions: ↵
- The elements in the array are chosen from the set {1, 2, ..., C}. ↵
- The maximum size of any subarray containing identical elements is at most B.↵
↵
↵
**Input**↵
↵
An integer A: the size of the array. (1<=A<=10^9)↵
↵
An integer B: the maximum size of a subarray containing identical elements. (1<=B<=min(50,A))↵
↵
An integer C: the maximum value for any element in the array (elements are chosen from {1, 2, ..., C}). (1<=C<=10^5)↵
↵
↵
**Output**↵
↵
An integer representing the number of valid arrays.(Return the value modulo 1e9+7)↵
↵
↵
**Example**↵
For ↵
A=3 , B=1 , C=3 the answer is 12 and the valid subarrays are↵
[1, 2, 1], [1, 2, 3], [1, 3, 1], [1, 3, 2], [2, 1, 2], [2, 1, 3], [2, 3, 1], [2, 3, 2], [3, 1, 2], [3, 1, 3], [3, 2, 1], [3, 2, 3]↵
↵
I am thinking of dp but how to handle such large A ? Is there any problem it could be reduced to ?
↵
I recently faced an interesting problem during a company online assessment, and I wanted to share it with you all. Unfortunately, I couldn't solve it, and I’m reaching out for your help.↵
↵
**Problem Description**↵
↵
You are given three integers: A,B,C. Your task is to count the number of possible arrays of size A that satisfy the following conditions: ↵
- The elements in the array are chosen from the set {1, 2, ..., C}. ↵
- The maximum size of any subarray containing identical elements is at most B.↵
↵
↵
**Input**↵
↵
An integer A: the size of the array. (1<=A<=10^9)↵
↵
An integer B: the maximum size of a subarray containing identical elements. (1<=B<=min(50,A))↵
↵
An integer C: the maximum value for any element in the array (elements are chosen from {1, 2, ..., C}). (1<=C<=10^5)↵
↵
↵
**Output**↵
↵
An integer representing the number of valid arrays.(Return the value modulo 1e9+7)↵
↵
↵
**Example**↵
For ↵
A=3 , B=1 , C=3 the answer is 12 and the valid subarrays are↵
[1, 2, 1], [1, 2, 3], [1, 3, 1], [1, 3, 2], [2, 1, 2], [2, 1, 3], [2, 3, 1], [2, 3, 2], [3, 1, 2], [3, 1, 3], [3, 2, 1], [3, 2, 3]↵
↵
I am thinking of dp but how to handle such large A ? Is there any problem it could be reduced to ?
