นับจำนวนการเรียงลำดับที่ลดลงก่อนแล้วเพิ่มขึ้นใน C++

เรามีตัวแปร num เป้าหมายคือหาจำนวนการเรียงลำดับของตัวเลขระหว่าง [1, num] ที่ตัวเลขลดลงก่อนแล้วเพิ่มขึ้น ตัวอย่างเช่นถ้า num=3 ตัวเลขคือ 1,2,3 การเรียงลำดับจะเป็น [3,1,2] และ [2,1,3] จำนวนคือ 2

เรารู้ว่าในทุกการเรียงลำดับ การเปลี่ยนจากการลดลงเป็นการเพิ่มขึ้นจะถูกกำหนดโดยตำแหน่งของ 1 ซึ่งเป็นตัวเลขน้อยที่สุด หลังจาก 1 ทุกตัวเลขจะเริ่มเพิ่มขึ้น สำหรับการเรียงลำดับที่ลดลงแล้วเพิ่มขึ้น 1 ควรอยู่ระหว่างตำแหน่ง 2 ถึง num-1 [ → ...1… → ]

ถ้า 1 อยู่ต้นข้อความ ชุดจะเพิ่มขึ้นทั้งหมด [ 1.. → ] ถ้าอยู่ท้ายจะลดลงทั้งหมด [ … → 1 ]

สมมติ num=4

วาง 1 ตำแหน่งที่ 2 [ - , 1, - , - ] สำหรับตำแหน่งแรกเลือกจาก (2,3,4) สมมติเลือก 2 ชุดจะเป็น [ 2,1,3,4] มี ³C₁ การเรียงลำดับ

วาง 1 ตำแหน่งที่ 3 [ -, -, 1, - ] เลือก 2 ตัวจาก 3 ตัว (2,3,4) จำนวนการเรียงลำดับคือ ³C₂

ดังนั้นจำนวนการเรียงลำดับรวม = ³C₁ + ³C₂ สำหรับ num=4

สำหรับ num = x จำนวนจะเป็น = ^x-1C₁ + ^x-1C₂+.....+^x-1C_x-2 = 2^x-1 - 2 จากทฤษฎีไบโนเมียล

มาดูตัวอย่าง

อินพุต − num=4

เอาต์พุต − จำนวนการเรียงลำดับที่ลดลงก่อนแล้วเพิ่มขึ้น คือ 6

คำอธิบาย − การเรียงลำดับจะเป็น −

[ 2, 1, 3, 4 ], [ 3, 1, 2, 4 ], [ 4, 1, 2, 3 ] → 1 อยู่ตำแหน่งที่ 2
[ 2, 3, 1, 4 ], [ 2, 4, 1, 3 ], [ 3, 4, 1, 2 ] → 1 อยู่ตำแหน่งที่ 3

อินพุต − num=6

เอาต์พุต − จำนวนการเรียงลำดับที่ลดลงก่อนแล้วเพิ่มขึ้น คือ 30

คำอธิบาย − ตัวอย่างการเรียงลำดับบางส่วน −

[ 2, 1, 3, 4, 5, 6 ], [ 3, 1, 2, 4, 5, 6 ], [ 4, 1, 2, 3, 5, 6 ], [ 5, 1, 2, 3, 4, 6 ], [ 6, 1, 2, 3, 4, 5 ] … [ 6, 5, 4, 3, 1, 2].

แนวทางที่ใช้ในโปรแกรม

ในแนวทางนี้เราใช้ทฤษฎีไบโนเมียลคำนวณการเรียงลำดับจากสูตรโดยตรง สร้างฟังก์ชัน value(long long i, long long num) คืนค่า inum

• รับตัวแปร num เป็นอินพุต
• ฟังก์ชัน permutations_increase_decrease(int num) รับ num คืนจำนวนการเรียงลำดับที่ลดลงก่อนแล้วเพิ่มขึ้นจากตัวเลข 1 ถึง num
• ฟังก์ชัน value(long long i, long long num) คำนวณ (i^num) % temp โดย temp=1000000007
• ใน permutations_increase_decrease(int num) กำหนด temp=1000000007
• ถ้า num เป็น 1 ไม่มีการเรียงลำดับ คืน 0
• มิฉะนั้น กำหนด count = (value(2, num - 1) - 2) % temp จากสูตร
• คืนค่า count เป็นผลลัพธ์

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

long long value(long long i, long long num){
    int temp = 1000000007;
    if (num == 0){
        return 1;
    }
    long long j = value(i, num / 2) % temp;
    j = (j * j) % temp;
    if(num & 1){
        j = (j * i) % temp;
    }
    return j;
}

int permutations_increase_decrease(int num){
    int temp = 1000000007;
    if (num == 1){
        return 0;
    }
    int count = (value(2, num - 1) - 2) % temp;
    return count;
}

int main(){
    int num = 4;
    cout<<"Count of permutations that are first decreasing then increasing are: "<<permutations_increase_decrease(num);
    return 0;
}

เอาต์พุต

หากรันโค้ดด้านบนจะได้ผลลัพธ์ดังนี้ −

Count of permutations that are first decreasing then increasing are: 6