zbrka.cpp

Bài toán

Đếm số lượng hoán vị của dãy 1..n mà có k cặp nghịch thế. Hai phần tử a[i], a[j] là một cặp nghịch thế khi và chỉ khi i<j và a[i]>a[j].

Độ phức tạp

O(n.k)

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

int F[1309][12309];

bool FF[1309][12309];

int f(int m, int n){

    if (n<0) return 0;

    if (n==0) return 1;

    if (m==0) return 0;

    if (FF[m][n]) return F[m][n];

    int r = (f(m, n-1) - f(m-1, n-m) + f(m-1, n)) % 1000000007;

    if (r<0) r += 1000000007;

    //printf("f(%d, %d) = %d\n", m, n, r);

    FF[m][n]=true;

    return F[m][n]=r;

}

main(){

    int m, n;

    scanf("%d%d", &m, &n);

    //m=1000, n=10000;

    for (int i=1; i<=m; i++) f(i,n);

    printf("%d\n", f(m, n));

}

Nhận xét

Gọi f(m,n) là số dãy hoán vị 1..m có n cặp nghịch thế. Bắt đầu từ một dãy hoán vị 1..m-1, có x cặp nghịch thế, thì ta cần đặt phần tử thứ m vào trước y số ở trong hoán vị 1..m-1 đã nói ở trên sao cho y+x=n. Suy ra ta có công thức f(m,n) = sum(f(m-1,n-i)) với i thuộc 0..m-1.

Mô tả

int f(int m, int n)

số hoán vị 1..m có n cặp nghịch thế

Các lỗi thường gặp

Wrong answer

- Quên chưa lấy mô đun.

- Quên câu lệnh if (r<0) r += 1000000007

Runtime error

- Mảng F quá bé

- Đệ quy quá sâu, theo lý thuyết thì lời gọi đệ quy như trên sẽ có độ sâu khoảng m.n, cần có lệnh sau để giảm độ sâu của đệ quy: for (int i=1; i<=m; i++) f(i,n);

Time limit exceeded

- Đệ quy quá sâu, giảm độ sâu bằng lệnh sau đây giúp chương trình chạy nhanh gấp đôi (thử nghiệm với m=1000 và n=10000): for (int i=1; i<=m; i++) f(i,n);