Welcome to Subscribe On Youtube
1866. Number of Ways to Rearrange Sticks With K Sticks Visible
Description
There are n
uniquelysized sticks whose lengths are integers from 1
to n
. You want to arrange the sticks such that exactly k
sticks are visible from the left. A stick is visible from the left if there are no longer sticks to the left of it.
 For example, if the sticks are arranged
[1,3,2,5,4]
, then the sticks with lengths1
,3
, and5
are visible from the left.
Given n
and k
, return the number of such arrangements. Since the answer may be large, return it modulo 10^{9} + 7
.
Example 1:
Input: n = 3, k = 2 Output: 3 Explanation: [1,3,2], [2,3,1], and [2,1,3] are the only arrangements such that exactly 2 sticks are visible. The visible sticks are underlined.
Example 2:
Input: n = 5, k = 5 Output: 1 Explanation: [1,2,3,4,5] is the only arrangement such that all 5 sticks are visible. The visible sticks are underlined.
Example 3:
Input: n = 20, k = 11 Output: 647427950 Explanation: There are 647427950 (mod 10^{9 }+ 7) ways to rearrange the sticks such that exactly 11 sticks are visible.
Constraints:
1 <= n <= 1000
1 <= k <= n
Solutions
Solution 1: Dynamic Programming
We define $f[i][j]$ to represent the number of permutations of length $i$ in which exactly $j$ sticks can be seen. Initially, $f[0][0]=1$ and the rest $f[i][j]=0$. The answer is $f[n][k]$.
Consider whether the last stick can be seen. If it can be seen, it must be the longest. Then there are $i  1$ sticks in front of it, and exactly $j  1$ sticks can be seen, which is $f[i  1][j  1]$. If the last stick cannot be seen, it can be any one except the longest stick. Then there are $i  1$ sticks in front of it, and exactly $j$ sticks can be seen, which is $f[i  1][j] \times (i  1)$.
Therefore, the state transition equation is:
\[f[i][j] = f[i  1][j  1] + f[i  1][j] \times (i  1)\]The final answer is $f[n][k]$.
We notice that $f[i][j]$ is only related to $f[i  1][j  1]$ and $f[i  1][j]$, so we can use a onedimensional array to optimize the space complexity.
The time complexity is $O(n \times k)$, and the space complexity is $O(k)$. Here, $n$ and $k$ are the two integers given in the problem.

class Solution { public int rearrangeSticks(int n, int k) { final int mod = (int) 1e9 + 7; int[][] f = new int[n + 1][k + 1]; f[0][0] = 1; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= k; ++j) { f[i][j] = (int) ((f[i  1][j  1] + f[i  1][j] * (long) (i  1)) % mod); } } return f[n][k]; } }

class Solution { public: int rearrangeSticks(int n, int k) { const int mod = 1e9 + 7; int f[n + 1][k + 1]; memset(f, 0, sizeof(f)); f[0][0] = 1; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= k; ++j) { f[i][j] = (f[i  1][j  1] + (i  1LL) * f[i  1][j]) % mod; } } return f[n][k]; } };

class Solution: def rearrangeSticks(self, n: int, k: int) > int: mod = 10**9 + 7 f = [[0] * (k + 1) for _ in range(n + 1)] f[0][0] = 1 for i in range(1, n + 1): for j in range(1, k + 1): f[i][j] = (f[i  1][j  1] + f[i  1][j] * (i  1)) % mod return f[n][k]

func rearrangeSticks(n int, k int) int { const mod = 1e9 + 7 f := make([][]int, n+1) for i := range f { f[i] = make([]int, k+1) } f[0][0] = 1 for i := 1; i <= n; i++ { for j := 1; j <= k; j++ { f[i][j] = (f[i1][j1] + (i1)*f[i1][j]) % mod } } return f[n][k] }

function rearrangeSticks(n: number, k: number): number { const mod = 10 ** 9 + 7; const f: number[][] = Array.from({ length: n + 1 }, () => Array.from({ length: k + 1 }, () => 0), ); f[0][0] = 1; for (let i = 1; i <= n; ++i) { for (let j = 1; j <= k; ++j) { f[i][j] = (f[i  1][j  1] + (i  1) * f[i  1][j]) % mod; } } return f[n][k]; }