Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Các cá thể được tạo ra bằng công nghệ biến đổi gen khi đưa ra nhân giống đại trà bằng phương pháp 

sinh sản hữu tính dần dần mất đi một số đặc tính quý báu có ở các thế hệ  ban đầu. Vấn đề ở chổ là 

các cá thể  thế  hệ  mới không giữ  được trọn vẹn các gen  quý của bố  và mẹ. Bản đồ  gen của mỗi cá 

thể  được biểu diễn dưới dạng xâu ký tự  S  chỉ  chứa các ký tự  la tinh  in  thường, mỗi ký tự  đại diện 

cho một gen.

Nếu bản đồ  gen của mẹ  / bố  là Sp, (cá thể  thế  hệ  F1) và bản đồ  gen của con sinh ra trực tiếp từ  cá 

thể này (thế hệ F2) là Sc thì Sc có các tính chất sau:

Sc có m ký tự đầu giống m ký tự đầu của Sp,

Sc có m ký tự cuối giống m ký tự cuối của Sp.

Nói một cách khác  Sc có tiền tố độ dài m trùng khớp với tiền tố độ dài m của Sp và Sc có hậu tố độ

dài m trùng khớp với hậu tố độ dài m của Sp. Nếu k là giá trị lớn nhất của các m thỏa mãn hai điều 

kiện trên thì cặp bản đồ Sp và Sc có “độ ổn định di truyền k”.

Trên cánh đồng thực nghiệm hiện có n cây đánh số từ 1 đến n, cây thứ i có bản đồ  gen là Si. i  = 

1÷ n. Người ta cần chọn một cặp cá thể có độ ổn định di truyền k để nghiên cứu. 

Hãy xác định q – số cặp khác nhau có thể lựa chọn. Hai cặp gọi là khác nhau nếu tồn tại một cây có 

ở cặp này và không có ở cặp kia. 

Dữ liệu: Vào từ file văn bản GENEMAP.INP:

Dòng đầu tiên chứa 2 số nguyên n và k (2 ≤ n ≤ 10

5

, 1 ≤ k ≤ 200),

Dòng thứ i trong n dòng sau chứa xâu Si,mỗi xâu có độ dài không quá 200.

Kết quả: Đưa ra file văn bản GENEMAP.OUT một số nguyên là phần dư của q chia cho 10

9

+7.
Các cá thể được tạo ra bằng công nghệ biến đổi gen khi đưa ra nhân giống đại trà bằng phương pháp sinh sản hữu tính dần dần mất đi một số đặc tính quý báu có ở các thế hệ  ban đầu. Vấn đề ở chổ là các cá thể  thế  hệ  mới không giữ  được trọn vẹn các gen  quý của bố  và mẹ. Bản đồ  gen của mỗi cá thể  được biểu diễn dưới dạng xâu ký tự  S  chỉ  chứa các ký tự  la tinh  in  thường, mỗi ký tự  đại diện cho một gen.
Nếu bản đồ  gen của mẹ  / bố  là Sp, (cá thể  thế  hệ  F1) và bản đồ  gen của con sinh ra trực tiếp từ  cá  thể này (thế hệ F2) là Sc thì Sc có các tính chất sau:
Sc có m ký tự đầu giống m ký tự đầu của Sp,
Sc có m ký tự cuối giống m ký tự cuối của Sp.
Nói một cách khác  Sc có tiền tố độ dài m trùng khớp với tiền tố độ dài m của Sp và Sc có hậu tố độ dài m trùng khớp với hậu tố độ dài m của Sp. Nếu k là giá trị lớn nhất của các m thỏa mãn hai điều kiện trên thì cặp bản đồ Sp và Sc có “độ ổn định di truyền k”.
Trên cánh đồng thực nghiệm hiện có n cây đánh số từ 1 đến n, cây thứ i có bản đồ  gen là Si. i  = 1÷ n. Người ta cần chọn một cặp cá thể có độ ổn định di truyền k để nghiên cứu. 
Hãy xác định q – số cặp khác nhau có thể lựa chọn. Hai cặp gọi là khác nhau nếu tồn tại một cây có ở cặp này và không có ở cặp kia. 
Dữ liệu: Vào từ file văn bản GENEMAP.INP:
Dòng đầu tiên chứa 2 số nguyên n và k (2 ≤ n ≤ 10^5, , 1 ≤ k ≤ 200),
Dòng thứ i trong n dòng sau chứa xâu Si,mỗi xâu có độ dài không quá 200.
Kết quả: Đưa ra file văn bản GENEMAP.OUT một số nguyên là phần dư của q chia cho 10^9+7.
Ví dụ: 
GENEMAP .INP   
5 2
aaaaaa
aabdecaa
aaaa
bbcaa
bbaaehaa
 GENEMAP.OUT
3