| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P178PROE - ROUND 8E - MINIONS |
Có N minion đang sống trong nhà của Gru. Nhà có M phòng với khả năng chứa số lượng không hạn chế các minion. Mỗi phòng sẽ có hai trạng thái: sẵn sàng và không sẵn sàng. Các minion chỉ được vào ở trong các căn phòng đã sẵn sàng. Và mỗi phòng đã sẵn sàng cũng sẽ chứa ít nhất 1 minion.
Gru muốn tính xem có bao nhiêu cách khác nhau để sắp xếp các phòng ở cho các minion. Ban đầu, tất cả N phòng đều sẵn sàng. Trong D ngày tiếp theo, Gru muốn tính xem có bao nhiêu cách khác nhau nếu thay đổi trạng thái một số phòng so với ngày hôm trước. Hai cách sắp xếp A và B được coi là giống nhau nếu với mỗi phòng trong cách A có số lượng minion là k thì cũng sẽ có một phòng trong cách B có số lượng tương tự.
Input
Dòng đầu ghi số bộ test, không quá 10. Mỗi bộ test gồm:
- Dòng đầu tiên ghi 3 số N,M,D (1<=M<=N, D<=100000).
- Tiếp theo là D dòng, mỗi dòng ghi hai số L và R (1<=L<=R<=M) cho biết các phòng có thứ tự từ L đến R sẽ được Gru đảo ngược trạng thái trong ngày đó.
Output
Với mỗi ngày trong danh sách, ghi ra tổng số cách sắp xếp khác nhau tìm được, chia modulo cho 880803841.
Example
Input: 2
3 3 2
2 2
1 3
5 5 3
1 3
2 2
1 5 Output: 3
1
15
25
15
| Được gửi lên bởi: | adm |
| Ngày: | 2017-04-17 |
| 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 ASM64 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 |
