สมมติว่าเรามีอาร์เรย์ที่ประกอบด้วย n ตัวเลขจาก 1 ถึง n เพิ่มขึ้น เราต้องหาจำนวนของความผิดปกติที่มันสามารถสร้างได้
เรารู้ว่าในคณิตศาสตร์แบบผสมผสาน ความคลาดเคลื่อนคือการเรียงสับเปลี่ยนขององค์ประกอบของเซต โดยที่องค์ประกอบจะไม่ปรากฏในตำแหน่งเดิม คำตอบอาจมีขนาดใหญ่มาก ดังนั้นให้ส่งคืน mod เอาต์พุต 10^9 + 7
ดังนั้น ถ้าอินพุตเท่ากับ 3 เอาต์พุตจะเป็น 2 เนื่องจากอาร์เรย์ดั้งเดิมคือ [1,2,3] ความแปรปรวนสองอย่างคือ [2,3,1] และ [3,1,2].
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ม :=10^9 + 7
-
กำหนดฟังก์ชัน add() ซึ่งจะใช้เวลา a, b,
-
กลับ ((a mod m) + (b mod m)) mod m
-
กำหนดฟังก์ชัน mul() ซึ่งจะใช้ a, b,
-
กลับ ((a mod m) * (b mod m)) mod m
-
จากวิธีหลักให้ทำดังนี้
-
ยกเลิก :=0
-
ถ้า n เท่ากับ 1 แล้ว −
-
คืนค่า 0
-
-
ถ้า n เท่ากับ 2 แล้ว −
-
กลับ 1
-
-
กำหนดขนาดอาร์เรย์ dp (n + 1)
-
dp[2] :=1
-
สำหรับการเริ่มต้น i :=3 เมื่อฉัน <=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));
} อินพุต
3
ผลลัพธ์
2
