Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

C11BC1 - The country of heaven

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/c11bc1


Một đất nước có N thành phố, mỗi thành phố được đặc trưng bởi 2 con số: A[i] và B[i] (trong đó: A[i] là khả năng tăng trưởng của thành phố đó và B[i] là “chỉ số ngôn ngữ” của thành phố đó). Một “liên minh” là 1 tập hợp gồm k thành phố trong N thành phố của đất nước (k <= N) và có ít nhất 2 thành phố khác nhau về chỉ số ngôn ngữ. “Khả năng liên minh” của k thành phố trong 1 liên minh được tính bằng tích các khả năng tăng trưởng của k thành phố đó. Khả năng tăng trưởng của đất nước sẽ được tính bằng tổng tất cả các khả năng liên minh của các liên minh, và tất cả các liên minh này đều khác nhau.

Ví dụ 1 liên minh gồm 5 thành phố là: 1, 4, 2, 5, 6 thì khả năng liên minh sẽ là A[1]*A[4]*A[2]*A[5]*A[6].

Hai liên minh được gọi là khác nhau nếu tồn tại "ít nhất" một thành phố có trong liên mình này mà không có trong liên minh kia.

Input

            Dòng đầu gồm 2 số n và k (2<= n <= 10^5, 2 <= k <= 50)

            N dòng tiếp theo: mỗi dòng gồm 2 số A[i] và B[i] (A[i] <= 1000 và B[i] <= 10^9)

Output

            Gồm 1 dòng duy nhất: Khả năng tăng trưởng của đất nước theo module 790972.

Example

Input:

            5 3

            4 1

            6 4

            5 3

            2 2

            3 5 Output:

            580

Time limit đã được thay đổi, những ai code chưa chuẩn thì code lại với cách tối ưu hơn.

Được gửi lên bởi:Duy Khanh Nguyen
Ngày:2011-10-01
Thời gian chạy:0.800s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C CPP PAS-GPC PAS-FPC
Nguồn bài:Từ trên trời rơi xuống

hide comments
2021-05-27 17:59:22
Tham khảo: https://vnspoj.github.io/problems/C11BC1
2019-10-28 13:22:36
90.91
5 3
4 3
6 3
5 3
2 3
3 3
2018-08-08 16:10:18
Nhật Hào sạch
2017-02-22 09:10:10
90.91 là do sai công thức nhé!!!!
2016-09-27 03:28:39
Code:
http://shink.in/06LFh
2016-09-07 17:40:13 minhsn
trâu cũng AC ax ax
2015-10-27 19:51:58
Blog Thuật toán SPOJ hy vọng giúp được cho mọi người : http://www.oni.vn/uR57W
2015-09-10 14:37:59 D.Centaur


Last edit: 2015-09-10 14:38:17
2015-06-18 01:17:45 Stupid Dog
không hiểu sao long long mới AC
2011-11-07 16:46:07 Tô Ngọc Linh
Bài này mình chết 1 test là TLE hay WA nhỉ :-(
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.