Pythonで隣接するk個のスワップと最大でk個のスワップの後にシーケンスの数を見つけるプログラム

最初のn個の自然数を持つ配列Aがあるとします。 Aで正確にk個の隣接するスワップの後に取得できるシーケンス（S1）の数を見つける必要がありますか？そして、Aで最大k回のスワップ後にいくつのシーケンス（S2）を取得できますか？ここで、隣接するスワップとは、インデックスiとi+1の要素を交換することを意味します。

したがって、入力がn =3 k =2の場合、-

元の配列は[1、2、3]

• 2つの隣接するスワップの後：[1、2、3]、[2、3、1]、[3、1、2]を取得できるため、S1 =3
• 最大2回のスワップ後：
  • 0スワップ後：[1、2、3]
  • 1回の交換後：[2、1、3]、[3、2、1]、[1、3、2]。
  • 2回のスワップ後：[1、2、3]、[2、3、1]、[3、1、2]

したがって、S2 =6

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

• p =10 ^ 9 + 7
• A：=1つの要素のみを持つ配列1
• C：=1つの要素のみを持つ配列1
• 2からn+1の範囲のnについては、
  • B：=A、A：=1つの要素のみを持つ配列1
  • D：=C、C：=1つの要素のみを持つ配列1
  • 1から最小（k + 1および1からnまでのすべての数値の合計）の範囲のxの場合
    • insert（Aの最後の要素+（x<の場合はB[x]、それ以外の場合は0のサイズ）-（0 <=x-nの場合はB[x-n]、それ以外の場合は0））mod p）Aの最後に
    >
  • 1からn-2の範囲のxについては、
    • Cの最後に（（D [x] +（n-1）* D [x-1]）mod p）を挿入します
  • Cの最後に（n * Dの最後の要素）modpを挿入します
• Aのすべての要素の合計を返す[インデックスkmod2からk]）modpおよびC[n-1およびkの最小値]

例

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

p = 10**9+7
def solve(n, k):
   A = [1]
   C = [1]
   for n in range(2,n+1):
      B = A
      A = [1]
      D = C
      C = [1]

      for x in range(1,min(k+1,n*(n-1)//2+1)):
         A.append((A[-1] + (B[x] if x<len(B) else 0) - (B[x-n] if 0<=x-n else 0)) % p )
      for x in range(1,n-1):
         C.append((D[x]+(n-1)*D[x-1]) % p)
      C.append(n*D[-1] % p)
   return sum(A[k%2:k+1:2]) % p,C[min(n-1,k)]

n = 3
k = 2
print(solve(n, k))

入力

3, 2

出力

3, 6