Editorial for Bedao Regular Contest 03 - KINDNESS


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Dễ dàng nhận thấy là các xâu khác xâu ban đầu nhận được bằng cách đổi chỗ ~2~ kí tự khác nhau. Gọi ~cnt_c~ là số lượng kí tự ~c~ có trong xâu và ~n~ là độ dài xâu trong xâu thì số xâu khác xâu ban đầu sẽ bằng: ~\frac{1}{2}\sum_{c=a}^{z} cnt_c\times(n-cnt_c)~

Tuy nhiên nếu trong xâu có kí tự ~c~ nào đó mà ~cnt_c>1~ thì khi đổi chỗ ~2~ kí tự giống nhau đó thì ta còn nhận được thêm xâu ban đầu. Nên nếu có ~cnt_c>1~ thì đáp án sẽ phải cộng thêm ~1~.

Độ phức tạp: ~O(n \times 26)~


Comments

Please read the guidelines before commenting.


There are no comments at the moment.