Editorial for Đếm HN
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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Đếm HN
Subtask 2: ~K \leq 10^3~
- Duy trì một biến ~cnt_H~ để đếm số kí tự
H
đã được duyệt qua. - Với mỗi kí tự
N
trong xâu ~S~, ghép kí tự đó với tất cả các kí tựH
ở trước đó.
- Duy trì một biến ~cnt_H~ để đếm số kí tự
Subtask 4:
- Xâu ~S~ có dạng ~XXX..X~, tạm gọi các phần xâu ~X~ liên tiếp là một
block
. - Có hai trường hợp xảy ra:
- Ký tự
H
vàN
cùng trong mộtblock
: Dùng phương pháp của subtask 2 để giải quyết. - Ký tự
H
vàN
ở khácblock
: Gọi số kí tựH
vàN
trong xâu ~X~ lần lượt là ~cnt_H~ và ~cnt_N~. Số cách chọn xâu conHN
cho trường hợp này là: ~\frac{k(k - 1)}{2} \times cnt_H \times cnt_N~.
- Xâu ~S~ có dạng ~XXX..X~, tạm gọi các phần xâu ~X~ liên tiếp là một
Code tham khảo
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
string x;
long long k;
int main(){
cin.tie(0)->sync_with_stdio(0);
freopen("DEMHN.INP", "r", stdin);
freopen("DEMHN.OUT", "w", stdout);
cin >> x >> k;
long long cntH = 0, cntN = 0, ans = 0;
for (int i = 0; i < x.size(); i++){
if(x[i] == 'H') cntH++;
else if(x[i] == 'N'){
cntN++;
ans = (ans + cntH) % MOD;
}
}
ans = (ans * k) % MOD;
ans = (ans + ((cntH * cntN) % MOD) * ((k * (k - 1)) / 2 % MOD)) % MOD;
cout << ans;
return 0;
}