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

The second house for every one
 
IndexTrợ giúpTìm kiếmThành viênĐăng kýĐăng Nhập

Share | 
 

 Dãy nghịch thế

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
littlelee
Admin
Admin


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

Bài gửiTiêu đề: Dãy nghịch thế   Fri 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


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

Bài gửiTiêu đề: Re: Dãy nghịch thế   Mon 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


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

Bài gửiTiêu đề: Re: Dãy nghịch thế   Mon 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




Bài gửiTiêu đề: Re: Dãy nghịch thế   Today at 21:29

Về Đầu Trang Go down
 
Dãy nghịch thế
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang
 Similar topics
-
» Những bài thuốc chữa nghẹt mũi
» THUẬN NGHỊCH ĐỘC & vỸ TAM THANH
» Nghệ thuật làm dâu
» Quà Ra mắt anh em!(Đỉnh cao của nghệ thuật quay lén!)
» 10 kĩ năng và nghệ thuật chinh phục bạn gái

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