どのようにこのハードコンビナトリアルを解決するには？

Question

これはコンテストの問題です（ACM ICPC南アメリカ2015）、問題が最も難しいです。

概要：与えられる整数N及びK、長さのNが≤整数からなる配列の数をカウント_I≤ Kであり、その中の任意のx ENCE iがjのがI < Jと_I = X満たし、一対が存在しなければならない - 1と_{J X} = 、すなわち最後のxの前には、ある時点でx-1が続きます。

例：N = 1000とK = 100溶液については、265428620モジュロ（10 + 7）と合同であるべきです。その他の例と詳細はthe problem descriptionにあります。

私は自分の知識のすべてを試しましたが、それを行う方法を知るためのポインタが必要です。私はパターンを見つけるために強引な力でいくつかのリストを印刷しましたが、私は成功しませんでした。

私はこの問題の正しい解決方法を得るためのアルゴリズムまたは数式を探しています。それはどんな言語でもよい。

EDIT：

私は、インターネット（この問題を説明し、誰か）で見つかった式を使用して問題を解決しました。しかし、私はそれをプログラムしたからといって、理解しているわけではないので、問題は開いたままです。私のコードは、（オンライン裁判官が受理を返します）ここにある：

#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ではPythonよりも100倍高速であるため、実行不可能でなければなりません）。だから問題は実際にあなたにショートカットを見つけさせる。

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を返します。