Как решить эту сложную комбинаторную?

Question

Это проблема конкурса (ACM ICPC South America 2015), это было самое сложное в задаче.

Резюме: данных целых чисел N и К, подсчитать число последовательностей длины N, состоящий из целых чисел ≤ _я ≤ K, при условии, что для любого x в этом разделе ENCE там должен быть парой I, J удовлетворяющих я < J и _я = х - 1 и _J = х, т.е. последним x предшествует x - 1 в какой-то момент.

Пример: для N = 1000 и К = 100 решения должен быть конгруэнтен по модулю 265428620 (10 + 7). Другие примеры и подробности можно найти в the problem description.

Я пробовал все, что я знаю, но мне нужны указатели, чтобы знать, как это сделать. Я даже распечатал несколько списков с грубой силой, чтобы найти шаблон, но мне это не удалось.

Я ищу алгоритм или формулу, которая позволяет мне найти правильное решение этой проблемы. Это может быть любой язык.

EDIT:

Я решил проблему, используя формулу я нашел в Интернете (кто-то, кто объяснил эту проблему). Однако только потому, что я запрограммировал его, это не значит, что я это понимаю, поэтому вопрос остается открытым. Мой код здесь (онлайн судья возвращает Accepted):

#include <bits/stdc++.h> 
using namespace std; 
typedef long long int ll; 

ll mod = 1e9+7; 
ll memo[5001][5001]; 

ll dp(int n, int k){ 

    // K can't be greater than N 
    k = min(n, k); 

    // if N or K is 1, it means there's only one possible list 
    if(n <= 1 || k <= 1) return 1; 
    if(memo[n][k] != -1) return memo[n][k]; 

    ll ans1 = (n-k) * dp(n-1, k-1); 
    ll ans2 = k * dp(n-1, k);  
    memo[n][k] = ((ans1 % mod) + (ans2 % mod)) % mod; 

    return memo[n][k]; 
} 

int main(){ 
    int n, q; 

    for(int i=0; i<5001; i++) 
     fill(memo[i], memo[i]+5001, -1); 

    while(scanf("%d %d", &n, &q) == 2){ 
     for(int i=0; i<q; i++){ 
      int k;   
      scanf("%d", &k);    
      printf("%s%lld", i==0? "" : " ", dp(n, k)); 
     } 
     printf("\n"); 
    } 
    return 0; 
} 

Наиболее важные линий являются рекурсивным вызовом, в частности, эти линии

ll ans1 = (n-k) * dp(n-1, k-1); 
ll ans2 = k * dp(n-1, k);  
memo[n][k] = ((ans1 % mod) + (ans2 % mod)) % mod; 

Answer 1

Здесь я показываю грубую алгоритм силы для проблема в python. Он работает для небольших чисел, но для очень больших чисел требуется слишком много времени. Для N = 1000 и K = 5 это уже невозможно (требуется более 100 лет времени для вычисления) (В C это также должно быть неосуществимо, так как C только в 100 раз быстрее, чем Python). Таким образом, проблема на самом деле заставляет вас найти ярлык.

import itertools 

def checkArr(a,K): 
    for i in range(2,min(K+1,max(a)+1)): 
     if i-1 not in a: 
      return False 
     if i not in a: 
      return False 
     if a.index(i-1)>len(a)-1-a[::-1].index(i): 
      return False 
    return True 

def num_sorted(N,K): 
    result=0 
    for a in itertools.product(range(1,K+1), repeat=N): 
     if checkArr(a,K): 
      result+=1 
    return result 

num_sorted(3,10) 

Он возвращает 6, как ожидалось.