Skip to content

1866. Number of Ways to Rearrange Sticks With K Sticks Visible 👍

  • Time: $O(nk)$
  • Space: $O(nk)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  long rearrangeSticks(int n, int k) {
    if (n == k)
      return 1;
    if (k == 0)
      return 0;
    if (dp[n][k])
      return dp[n][k];
    return dp[n][k] = (rearrangeSticks(n - 1, k - 1) +
                       rearrangeSticks(n - 1, k) * (n - 1)) %
                      kMod;
  }

 private:
  static constexpr int kMod = 1'000'000'007;
  vector<vector<int>> dp = vector<vector<int>>(1001, vector<int>(1001));
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  public int rearrangeSticks(int n, int k) {
    if (n == k)
      return 1;
    if (k == 0)
      return 0;
    if (dp[n][k] != 0)
      return dp[n][k];
    return dp[n][k] = (int) (((long) rearrangeSticks(n - 1, k - 1) +
                              (long) rearrangeSticks(n - 1, k) * (n - 1)) %
                             kMod);
  }

  private static final int kMod = 1_000_000_007;
  private int[][] dp = new int[1001][1001];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
  @functools.lru_cache(None)
  def rearrangeSticks(self, n: int, k: int) -> int:
    if n == k:
      return 1
    if k == 0:
      return 0
    return (self.rearrangeSticks(n - 1, k - 1) +
            self.rearrangeSticks(n - 1, k) * (n - 1)) % self.kMod

  kMod = 1_000_000_007