ধরুন আমাদের ক্রমবর্ধমান ক্রমানুসারে 1 থেকে n পর্যন্ত n সংখ্যা নিয়ে গঠিত একটি অ্যারে আছে, আমাদের এটি তৈরি করতে পারে এমন বিভ্রান্তির সংখ্যা খুঁজে বের করতে হবে।
আমরা জানি যে সমন্বিত গণিতে, একটি ডিরেঞ্জমেন্ট হল একটি সেটের উপাদানগুলির একটি স্থানান্তর, যাতে কোনও উপাদান তার আসল অবস্থানে উপস্থিত হবে না। উত্তরটি অনেক বড় হতে পারে, তাই আউটপুট মোড 10^9 + 7 ফেরত দিন।
সুতরাং, যদি ইনপুট 3 এর মত হয়, তাহলে আউটপুট হবে 2, যেমন মূল অ্যারে [1,2,3]। দুটি বিভ্রান্তি হল [2,3,1] এবং [3,1,2]।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
m :=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
ফেরত দিন -
মূল পদ্ধতি থেকে নিম্নলিখিতগুলি করুন
-
ret :=0
-
যদি n 1 এর সমান হয়, তাহলে −
-
রিটার্ন 0
-
-
যদি n 2 এর সমান হয়, তাহলে −
-
রিটার্ন 1
-
-
আকারের একটি অ্যারে ডিপি সংজ্ঞায়িত করুন (n + 1)
-
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));
} ইনপুট
3
আউটপুট
2
