C++에서 배열의 교란 찾기

<시간/>

1에서 n까지의 n개의 숫자로 구성된 배열이 오름차순으로 있다고 가정하면 생성할 수 있는 혼란의 수를 찾아야 합니다.

조합 수학에서 교란은 집합의 요소가 원래 위치에 나타나지 않도록 하는 순열이라는 것을 알고 있습니다. 답은 매우 클 수 있으므로 출력 모드 10^9 + 7을 반환합니다.

따라서 입력이 3과 같으면 원래 배열이 [1,2,3]이므로 출력은 2가 됩니다. 두 가지 교란은 [2,3,1] 및 [3,1,2]입니다.

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

m :=10^9 + 7
add() 함수를 정의하면, b,
return ((a mod m) + (b mod m)) mod m
mul() 함수를 정의하면, b,
return ((a mod m) * (b mod m)) mod m
기본 방법에서 다음을 수행하십시오.
ret :=0
n이 1과 같으면 -
- 0 반환
n이 2와 같으면 -
- 1 반환
(n + 1) 크기의 배열 dp 정의
dp[2] :=1
i:=3 초기화의 경우, i <=n일 때 업데이트(i를 1만큼 증가), -
- dp[i] :=mul(i - 1, add(dp[i - 2], dp[i - 1]))
반환 dp[n]

예

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

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;
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:
   int findDerangement(int n) {
      int ret = 0;
      if (n == 1)
         return 0;
      if (n == 2)
         return 1;
      vector dp(n + 1);
      dp[2] = 1;
      for (int i = 3; i <= n; i++) {
         dp[i] = mul(i - 1, add(dp[i - 2], dp[i - 1]));
      }
      return dp[n];
   }
};
main(){
   Solution ob;
   cout<<(ob.findDerangement(3));
}