Nội dung Bài tập
- Mã:
- ACM2016_North_E
- Tên:
- Connecting points (ACM 2016 Miền Bắc)
- Dạng thi:
- acm
- Thang điểm:
- 1 điểm
- Giới hạn thời gian:
- 15 giây
- Giới hạn bộ nhớ:
- 64 MB
- Được tạo bởi:
- admin
On a circle, there are N points numbered 1 to N closewise. We want to connect these
points using some straight lines such that:
Your task is to count ways of connecting these N points modulo 109 + 7.
Input
points using some straight lines such that:
• Each point can connect directly to exactly 1 other point or does not have any connection.A way of connecting points can be represented using a one-dimensional array C where:
• There is no pair of connections which intersect each other.
• Cu< = u if point u does not connect to any other points.2 ways of connecting points C1 and C2 are considered different if exists u where C1u ≠ C2u.
• Cu< = v ≠ u if point u connect to point v.
• If Cu< = v then Cv = u.
Your task is to count ways of connecting these N points modulo 109 + 7.
Input
The input starts with the number of test - T (T ≤ 100). Then T tests follow. Each test is printed in a line with an integer N. (N ≤ 107)Output
For each test in the input, print the answer in a single line.
Sample
- input1
3output4
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
#include <iostream>using namespace std;struct ps { int tu, mau; &...