Python에서 가능한 겸손 행렬의 수를 계산하는 프로그램

<시간/>

두 개의 값 n과 m이 있다고 가정합니다. n x m 차수의 겸손한 행렬의 가능한 배열의 수를 찾아야 합니다. 매트릭스는 다음과 같은 경우 겸손하다고 합니다.

1~n x m 범위의 각 요소를 정확히 한 번만 포함합니다.
두 인덱스 쌍(i1, j1) 및 (i2, j2)에 대해 (i1 + j1) <(i2 + j2)이면 Mat[i1, j1]

답이 너무 크면 결과 모드 10^9 + 7을 반환합니다.

따라서 입력이 n =2 m =2와 같으면 두 개의 가능한 행렬이 있기 때문에 출력은 2가 됩니다. -

1	2
3	4

그리고

1	3
2	4

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

p :=10^9+7
결과:=값이 1인 목록
2에서 10^6 범위의 x에 대해 다음을 수행합니다.
- temp :=결과의 마지막 요소
- temp :=(temp*x) 모드 p
- 결과 끝에 temp 삽입
m> n이면
- 온도 :=n
- n :=m
- m :=온도
생산량:=1
1~m 범위의 x에 대해 다음을 수행합니다.
- prod :=(prod * 결과[x-1]) 모드 p
- prod :=(prod^2) 모드 p
0 ~ n - m 범위의 x에 대해
- prod :=(prod * 결과[m-1]) 모드 p
반품

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

p = 10**9+7

def solve(n, m):
   result = [1]
   for x in range(2,10**6+1):
      temp = result[-1]
      temp = (temp*x) % p
      result.append(temp)

   if(m > n):
      temp = n
      n = m
      m = temp
   prod = 1
   for x in range(1,m):
      prod = (prod * result[x-1]) % p
   prod = (prod**2) % p
   for x in range(n-m+1):
      prod = (prod*result[m-1]) % p
   return prod

n = 3
m = 3
print(solve(n, m))

입력

3, 3