Блог пользователя AngelKnows

Автор AngelKnows, история, 4 года назад, По-английски

Problem: Suppose $$$cnt(i)$$$ represents the number of occurrences of $$$i$$$ in array $$$A$$$ of length $$$n$$$ whose elements are between $$$1$$$ and $$$n$$$. An array is called a $$$k$$$-good array if and only if $$$cnt(k)=k$$$. Let $$$f(k)$$$ be the number of all $$$k$$$-good arrays. You are to calculate the $$$\sum\limits_{k=1}^n f(k)$$$.

This problem looks like some dp problems which can be reduced to a simper form and solved by Kunth's Mechanical Summation. But I haven't thought up a good solution.

Could you share your ideas about this problem?

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by AngelKnows (previous revision, new revision, compare).

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Can you also add constraints and the problem link? People often ask for problems from a running contest, so it's good to add a link to the problem. Constraints are also important, as they tell you what kind of approaches to consider.

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

The answer is $$$n^n - (n-1)^n$$$.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    $$$ \begin{equation} \begin{aligned} \sum_{k=1}^{n}f(k)&=\sum_{k=1}^{n}\binom{n}{k}(n-1)^{n-k} \\ &=\sum_{k=0}^{n}\binom{n}{k}(n-1)^{n-k}1^k-\binom{n}{0}(n-1)^n \\ &=n^n-(n-1)^n \end{aligned} \end{equation} $$$
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I don't think $$$f(k)=C(n,k)(n-1)^{n-k}$$$, because there should be only one k satisfying $$$cnt(k)=k$$$. For instance, $$$2,2,3,3,3$$$ is not 3-good array because we have both $$$cnt(3)=3$$$ and $$$cnt(2)=2$$$.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

If N is small, I can think of using inclusion-exclusion, what are the constraints of this problem?