Bedao OI Contest 5 - Sắp xếp chữ cái
Xem dạng PDF
Vì đạt được thành tích cao trong kỳ thi HSGQG vừa qua, bố mẹ Via quyết định tặng cậu ~n~ bộ đồ chơi xếp hình được đánh số từ ~1~ đến ~n~. Bộ đồ chơi thứ ~i~ bao gồm ~a_i~ ký tự ~A~ và ~b_i~ ký tự ~B~. Via đưa ra một trò chơi như sau:
Đầu tiên Via sẽ chọn ra 2 bộ đồ chơi xếp hình trong ~n~ bộ, nhóm các ký tự ~A~ và ký tự ~B~ của 2 bộ đã chọn rồi xếp chúng thành một hàng ngang. Ví dụ là có 3 chữ cái ~A~ và 4 chữ cái ~B~ thì ~ABABABB~ và ~BBBBAAA~ là một trong các cách xếp hợp lệ, và ~AAAABBB~ là một trong các cách xếp không hợp lệ.
Via muốn biết: có bao nhiêu cách chọn bộ và xếp chữ như vậy? Hai cách là khác nhau khi hai bộ xếp chữ được chọn ở hai cách là khác nhau, hoặc cách xếp nhận được là khác nhau.
Vì số cách chọn và xếp có thể rất lớn, bạn hãy in ra số cách tìm được chia lấy dư cho ~10^9 + 7~.
Input
Dữ liệu vào từ file văn bản ordletter.inp:
Dòng đầu tiên chứa số nguyên dương ~n~ — là số bộ đồ chơi mà Via được tặng (~2 \le n \le 2 \cdot 10^5~).
~n~ dòng tiếp theo, gồm hai số nguyên ~a_i~ và ~b_i~ — lần lượt là số ký tự ~A~ và số ký tự ~B~ của bộ đồ chơi thứ ~i~ (~1 \le a_i, b_i \le 2000~).
Output
In ra file văn bản ordletter.out một số nguyên duy nhất là số cách chọn bộ và xếp chữ tìm được, modulo ~10^9 + 7~.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| ~1~ | ~10 \%~ | ~n \le 5; a_i, b_i \le 10~ |
| ~2~ | ~20 \%~ | ~n \le 2000~ |
| ~3~ | ~20 \%~ | ~a_i, b_i \le 50~ |
| ~4~ | ~50 \%~ | Không có ràng buộc gì thêm |
Sample Input 1
2
1 1
2 1
Sample Output 1
10
Bình luận
include<bits/stdc++.h>
using namespace std;
define ll long long
define FOR(i,l,r) for(auto i = l; i <= r; i++)
define FORD(i,r,l) for(auto i = r; i >= l; i--)
define MOD 1000000007
define N 200005
int n; int a[N], b[N]; ll dp[4005][4005]; ll f[N], finv[N];
ll pw(ll a, int b){ ll Ans = 1; int LOG = 31 - _builtinclz(b); FOR(i, 0, LOG){ if(b>>i&1) Ans = Ans * a % MOD; a = a * a % MOD; }
}
ll C(int k, int n){ return f[n] * finv[k] % MOD * finv[n-k] % MOD; }
inline void add(ll &a, ll b){ a += b; if(a >= MOD) a -= MOD; if(a < 0) a += MOD; }
inline void Solve(){ cin >> n; FOR(i, 1, n){ cin >> a[i] >> b[i]; dp[2000 + a[i]][2000 + b[i]]++; }
}
int main(){ iosbase::syncwith_stdio(0); cin.tie(0); cout.tie(0);
}
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.