| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P166SUMB - ROUND 6B - Katana |
Katana không những là một cô nàng xinh đẹp, mà còn là một samurai có võ thuật cao cường và tinh thông kiếm pháp. Tại Nhật Bản, quê hương của cô có n loại đồng xu khác nhau. Với mỗi loại đồng xu i sẽ có mệnh giá ai đồng tương tứng. Có thể có trường hợp i # j những ai = aj.
Katana nợ Rick Flag (chỉ huy của team) t đồng, và cô phải dùng số đồng xu mà mình có để trả nợ. Nhưng Flag không phải người dễ tính, anh đưa ra q cặp số nguyên bi và ci (1 <= i <= q) và anh yêu cầu số đồng xu loại bi phải có số lượng lớn hơn số đồng xu loại ci (Tất cả bi khác nhau từng đôi một và tất cả ci khác nhau từ đôi một)
Các bạn hãy giúp Katana tính xem có tất cả bao nhiêu cách chọn đồng xu các loại để trả đúng t đồng cho Flag mà vẫn thỏa mãn yêu cầu của anh ta. Biết 2 cách khác nhau khi mà tồn tại 1 loại đồng xu i có số lượng khác nhau ở 2 cách chọn.
Nếu không có cách nào thỏa mãn, in ra 0.
Input
Dòng đầu tiên nhập 3 số nguyên n, q, t (1 <= n <= 300; 0 <= q <= n; 1 <= t <= 105).
Dòng thứ 2 nhập mảng a1, …, an (1 <= ai <= 105) là số mệnh giá của từng loại tiền tương ứng.
q dòng tiếp theo, mỗi dòng nhập 2 số bi và ci (1 <= i <= q; 1 <= bi, ci <= n; bi # ci). Input đảm bảo tất cả phần tử mảng b đều khác nhau, và mảng c cũng vậy
Output
In ra kết quả của bài toán – số cách thỏa mãn lấy dư cho 109 + 7.
Example
Test 1:
Input:
3 2 10
1 2 3
1 2
2 1
Output:
0
Test 2:
Input:
4 2 17
3 1 2 5
4 2
3 4
Output:
3
Giải thích test 2: 17 đồng có tất cả 3 cách chia mà thỏa mãn yêu cầu của Flag
(0 loại 1, 1 loại 2, 3 loại 3, 2 loại 4), (0, 0, 6, 1), (2, 0, 3, 1)
| Được gửi lên bởi: | adm |
| Ngày: | 2016-08-12 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
