Untitled

mail@pastecode.io avatar
unknown
plain_text
2 months ago
738 B
4
Indexable
Never
int n = level.size();
  unordered_map<int, int> level_counts;
  for (int lvl : level) {
    level_counts[lvl]++;
  }

  int odd_levels = 0;
  for (auto p : level_counts) {
    if (p.second % 2 != 0) {
      odd_levels++;
    }
  }

  if (odd_levels > k) {
    return 0;
  }

  int mod = 1e9 + 7;
  vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
  dp[0][0] = 1;

  for (int i = 1; i <= n; i++) {
    int lvl = level[i - 1];
    for (int j = 0; j <= k; j++) {
      dp[i][j] = dp[i - 1][j];
      if (j > 0 && (level_counts[lvl] % 2 == 0 || odd_levels + 1 <= k)) {
        dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % mod;
      }
    }

    if (level_counts[lvl] % 2 != 0 && j == 0) {
      dp[i][j] = 1;
    }
  }

  return dp[n][k];
Leave a Comment