Diễn đàn tin học Nguyễn Văn Linh
Bạn có muốn phản ứng với tin nhắn này? Vui lòng đăng ký diễn đàn trong một vài cú nhấp chuột hoặc đăng nhập để tiếp tục.

Diễn đàn tin học Nguyễn Văn Linh

The second house for every one
 
Trang ChínhLatest imagesTìm kiếmĐăng kýĐăng Nhập

 

 Dãy nghịch thế

Go down 
Tác giảThông điệp
littlelee
Admin
Admin
littlelee


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 29
Đến từ : Nghĩa địa

Dãy nghịch thế Empty
Bài gửiTiêu đề: Dãy nghịch thế   Dãy nghịch thế I_icon_minitimeFri 19 Mar 2010, 18:10

Dãy nghịch thế độ dài K


Cho dãy N số nguyên dương A[1] , … A[N] là một hoán vị của 1 , 2 , 3 , … N .
Một dãy nghịch thế độ dài k là 1 dãy A[j1] > A[j2] > A[j3] … > A[jk] với j1 < j2 < j3 … < jk . Hãy đếm xem có tất cả bao nhiêu dãy nghịch thế độ dài k .
Input

Dòng 1 : 2 số nguyên dương N và k ( 2 ≤ N ≤ 10000 , 2 ≤ k ≤ 10 ) .
Dòng 2 : N số nguyên dương A[1] … A[N] .
Output

Giả sử T là số lượng dãy nghịch thế có độ dài k , hãy ghi ra T mod 10^9 .
Example

Input:
3 2
3 2 1

Output:
3
Về Đầu Trang Go down
littlelee
Admin
Admin
littlelee


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 29
Đến từ : Nghĩa địa

Dãy nghịch thế Empty
Bài gửiTiêu đề: Re: Dãy nghịch thế   Dãy nghịch thế I_icon_minitimeMon 22 Mar 2010, 18:16

Bài này mình không có thuật toán nào hay cả. Với thuật toán O(n^2) thì không biết sẽ chạy trong bao lâu nhỉ.

Tuy nhiên công việc chỉ là đếm nên mình nghĩ với O(n^2) thì sẽ chạy không lâu lắm. Để thử đã.
Về Đầu Trang Go down
littlelee
Admin
Admin
littlelee


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 29
Đến từ : Nghĩa địa

Dãy nghịch thế Empty
Bài gửiTiêu đề: Re: Dãy nghịch thế   Dãy nghịch thế I_icon_minitimeMon 22 Mar 2010, 18:18

O sorry nhầm. Không phải thuật toán O(n^2) mà là đệ quy. Mình nghĩ nông cạn quá. Thôi, với n=10 000 thì đệ quy không được rồi frown
Về Đầu Trang Go down
Sponsored content





Dãy nghịch thế Empty
Bài gửiTiêu đề: Re: Dãy nghịch thế   Dãy nghịch thế I_icon_minitime

Về Đầu Trang Go down
 
Dãy nghịch thế
Về Đầu Trang 
Trang 1 trong tổng số 1 trang

Permissions in this forum:Bạn không có quyền trả lời bài viết
Diễn đàn tin học Nguyễn Văn Linh :: Góc tin học :: Lớp chuyên tin-
Chuyển đến