C++ですべての有効な集配オプションを数える

n個の注文のリストがあり、各注文に集配サービスがあるとします。配達[i]が常に集荷[i]の後にあるように、すべての有効な集荷/配達可能なシーケンスをカウントする必要があります。答えは非常に大きい可能性があるため、10 ^ 9+7を法として返します。

したがって、入力が2の場合、出力は6になります。これは、すべての可能な順序が（P1、P2、D1、D2）、（P1、P2、D2、D1）、（P1、D1、P2、D2）であるためです。 、（P2、P1、D1、D2）、（P2、P1、D2、D1）および（P2、D2、P1、D1）。また、集荷2は配達2の後なので、注文（P1、D2、P2、D1）は無効です。

これを解決するには、次の手順に従います-

• m：=1 ^ 9 + 7

• N：=550

• サイズの配列dpを定義します：（N + 5）x（N + 5）。これを-1で埋めます

• 関数add（）を定義します。これには、a、b、

  が必要です。

• return（（a mod m）+（b mod m））mod m

• 関数mul（）を定義します。これにはa、b、

  が必要です。

• return（（a mod m）*（b mod m））mod m

• 関数solve（）を定義します。これには、inPickup、left、i、j、

  が必要です。

• iが0と同じで、jが0と同じ場合、-

  • 1を返す

• dp [i、j]が-1に等しくない場合、-

  • dp [i、j]

    を返します

• ret：=0

• i> 0の場合、-

  • ret：=add（ret、mul（left、solve（inPickup + 1、left-1、i-1、j）））

• j> iの場合、

  • ret：=add（ret、mul（inPickup、solve（inPickup-1、left、i、j-1）））

• dp [i、j] =ret

  を返します

• メインの方法から、次のようにします-

• 戻り値solve（0、n、n、n）

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int m = 1e9 + 7;
const int N = 550;
int dp[N + 5][N + 5];
lli add(lli a, lli b){
   return ((a % m) + (b % m)) % m;
}
lli mul(lli a, lli b){
   return ((a % m) * (b % m)) % m;
}
class Solution {
   public:
   void pre(){
      for (int i = 0; i < N; i++) {
         for (int j = 0; j < N; j++) {
            dp[i][j] = -1;
         }
      }
   }
   int solve(int inPickup, int left, int i, int j){
      if (i == 0 && j == 0)
      return 1;
      if (dp[i][j] != -1)
      return dp[i][j];
      int ret = 0;
      if (i > 0) {
         ret = add(ret, mul(left, solve(inPickup + 1, left - 1, i
         - 1, j)));
      }
      if (j > i) {
         ret = add(ret, mul(inPickup, solve(inPickup - 1, left, i,
         j - 1)));
      }
      return dp[i][j] = ret;
   }
   int countOrders(int n){
      pre();
      return solve(0, n, n, n);
   }
};
main(){
   Solution ob;
   cout << (ob.countOrders(2));
}

入力

2

出力

6