https://www.hackerrank.com/contests/101hack44/challenges/palindromic-subsets
如果有3个a。2个b。1个c。
每个a看成不同的，那么能选出多少个不同的回文串呢？
从回文串入手，因为回文串最多只有1种字母是奇数个。
那么，如果我能快速算区间[L, R]中各种字母出现的次数，就好了。
假设上面的数据，所得到的回文串是：
a取奇数个：2^2 * 2^1（b只能取偶数个） * 2^0（C是偶数个，这个时候是空集）
然后再枚举b取奇数个，其他取偶数个。
最后，还有一种情况，就是全部都是偶数个，这个时候因为可能选到的全部都是空集，所以最后结果要减去1.
接下来就是快速计算了。明显线段树，一开始不知道怎么维护区间，
其实区间更新，很简单，因为字母的数量是不会变的，对于区间存在2个a的话，反转1次，就只是2个b。
所以只需要枚举26个字母，cnt[(i + k) % 26] = cnt[i]
意思是产生这个字母的个数是有它来产生的。然后线段树更新即可。
线段树写了很多次，看模板才想起怎么lazy--update 苦逼。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #define root 1, n, 1 #define lson L, mid, cur << 1 #define rson mid + 1, R, cur << 1 | 1 const int maxn = 1e5 + 20; char str[maxn]; const int MOD = 1e9 + 7; char to[222]; int add[maxn << 2]; LL quick_pow(LL a, LL b, int MOD) { LL ans = 1; assert(b >= 0); while (b) { if (b & 1) { ans = ans * a; if (ans >= MOD) ans %= MOD; } b >>= 1; a *= a; if (a >= MOD) a %= MOD; } return ans; } struct node { int cnt[26 + 2]; } seg[maxn << 2]; void toget(struct node &a, int val) { int cnt[26 + 2] = {0}; for (int i = 0; i < 26; ++i) { cnt[i] = a.cnt[i]; } for (int i = 0; i < 26; ++i) { a.cnt[(i + val) % 26] = cnt[i]; } return; } void pushUp(int cur) { for (int i = 0; i < 26; ++i) { seg[cur].cnt[i] = seg[cur << 1].cnt[i] + seg[cur << 1 | 1].cnt[i]; } } void pushDown(int cur) { if (add[cur]) { add[cur << 1 | 1] += add[cur]; add[cur << 1 | 1] %= 26; add[cur << 1] += add[cur]; add[cur << 1] %= 26; toget(seg[cur << 1], add[cur]); toget(seg[cur << 1 | 1], add[cur]); add[cur] = 0; } } void build(int L, int R, int cur) { if (L == R) { seg[cur].cnt[str[L] - 'a'] = 1; return; } int mid = (L + R) >> 1; build(lson); build(rson); pushUp(cur); } void upDate(int be, int en, int val, int L, int R, int cur) { if (L >= be && R <= en) { toget(seg[cur], val); add[cur] += val; add[cur] %= 26; return; } pushDown(cur); int mid = (L + R) >> 1; if (mid >= be) upDate(be, en, val, lson); if (mid < en) upDate(be, en, val, rson); pushUp(cur); } int query(int be, int en, int ch, int L, int R, int cur) { if (L >= be && R <= en) { return seg[cur].cnt[ch]; } pushDown(cur); int mid = (L + R) >> 1; int lans = 0, rans = 0; if (mid >= be) lans = query(be, en, ch, lson); if (mid < en) rans = query(be, en, ch, rson); return lans + rans; } void work() { for (int i = 'a'; i <= 'z' - 1; ++i) { to[i] = i + 1; } to['z'] = 'a'; int n, q; scanf("%d%d", &n, &q); scanf("%s", str + 1); build(root); while (q--) { int flag, L, R; scanf("%d", &flag); if (flag == 2) { scanf("%d%d", &L, &R); L++; R++; LL ans = 1; int len = 0; for (int i = 0; i < 26; ++i) { int ret = query(L, R, i, root); if (ret > 0) len++; else continue; ans = ans * quick_pow(2, ret - 1, MOD); if (ans >= MOD) ans %= MOD; } ans *= (len + 1); ans %= MOD; ans = (ans - 1 + MOD) % MOD; cout << ans << endl; } else { int t; scanf("%d%d%d", &L, &R, &t); L++; R++; upDate(L, R, t % 26, root); // printf("%d**** ", query(3, 3, 'u' - 'a', root)); } } // cout << query(1, n, 'o' - 'a', root) << endl; } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }