牛牛的字符串
观察题目性质,发现交换的元素 mod K 相等,按照 mod K 进行分类后变成了相邻交换。
那么在 mod K 意义下,不同的东西是独立的。所以拆成 K 个序列。
答案是有多少对 i < j,使得 K | (j - i) 且
考虑这个东西怎么求,发现他就是一个顺序对(跟逆序对类似)的个数。
那么可以用树状数组或者归并排序等方式直接做,复杂度O(nlogn)。
或者考虑这个题字符串由小写字母组成,所以维护一下到当前位置的前缀数量即可,复杂度O(26*n)。
#define rep0(i, n) for(int i = 0; i < n; i ++) class Solution { public: /** * * @param s string字符串 * @param k int整型 * @return int整型 */ int string(string s, int K) { // write code here int n = s.size(); int ans = 0; rep0(i, K) { vector<int> cnt(26); for(int j = i; j < n; j += K) { for(int x = 0; x < s[j] - 'a'; x ++) ans += cnt[x]; cnt[s[j] - 'a'] ++; } } return ans; } };