HDU 5239 Doom（线段树）

2019-04-14 21:08发布

站内文章 / 模拟电子
15077 0 1798
题意：给出一个长度为n的序列，和m次查询，每次查询一个区间的和，但查询之后把区间内每个点的值平方一次，所有的结果模上9223372034707292160。
其实这题一点也不难。。。 一个数又平方又模的次数多了以后，会维持在一个固定的值不动。打表可以发现规律，但是仔细想想也是可以想明白的。如果x的素因子的集合包含模的素因子集合，那么经过足够多的次数之后，取模会直接为0；反之，据费马小定理，则会维持一个固定的值不变。
另外模没有超过ULL的一半，不需要CRT。。。（其实是写不对ULL的CRT。。似乎是扩展欧几里得那里有点问题
（用了输入输出挂，，另外把模改成减法了）
#include #include #include #include #include #include #include using namespace std; #define ULL unsigned long long const ULL MOD = 9223372034707292160LL; const int MAXN = 100010; const int MAXL = 30; template inline int RD(T &x) { x = 0; char ch = getchar(); while(!isdigit(ch)) { ch = getchar(); if(ch == EOF) return 0; } while(isdigit(ch)) { x *= 10; x += ch - '0'; ch = getchar(); } return 1; } template void PT(T x) { if(x / 10) PT(x / 10); putchar(x % 10 + '0'); } ULL val[MAXN][MAXL]; ULL sum[MAXN << 2]; int cnt[MAXN << 2]; void Build(int l, int r, int rt) { cnt[rt] = 0; if(l >= r) { sum[rt] = val[l][0]; return ; } int m = (l + r) >> 1; Build(l, m, rt << 1); Build(m + 1, r, rt << 1 | 1); sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; if(sum[rt] > MOD) sum[rt] -= MOD; } void Update(int l, int r, int rt) { cnt[rt]++; if(l >= r) { sum[rt] = val[l][cnt[rt]]; return ; } int m = (l + r) >> 1; if(cnt[rt << 1] < MAXL - 1) Update(l, m, rt << 1); if(cnt[rt << 1 | 1] < MAXL - 1) Update(m + 1, r, rt << 1 | 1); sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; if(sum[rt] > MOD) sum[rt] -= MOD; } ULL Query(int L, int R, int l, int r, int rt) { if(L <= l && r <= R) { ULL ret = sum[rt]; if(cnt[rt] < MAXL - 1) Update(l, r, rt); return ret; } int m = (l + r) >> 1; ULL lch = 0, rch = 0, ret; if(L <= m) lch = Query(L, R, l, m, rt << 1); if(R > m) rch = Query(L, R, m + 1, r, rt << 1 | 1); sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; if(sum[rt] > MOD) sum[rt] -= MOD; ret = lch + rch; if(ret > MOD) ret -= MOD; return ret; } ULL Add_Mod(ULL x, ULL y) { ULL ret = 0, p = x, k = y; while(k) { if(k % 2 == 1) { ret += p; if(ret > MOD) ret -= MOD; } p += p; if(p > MOD) p -= MOD; k /= 2; } return ret; } int main() { // freopen("D.in", "r", stdin); int t, cas = 0; ULL cd; RD(t); while(t--) { putchar('C'); putchar('a'); putchar('s'); putchar('e'); putchar(' '); putchar('#'); PT(++cas); putchar(':'); puts(""); int n, m, a, b; RD(n), RD(m); for(int i = 1; i <= n; i++) { RD(val[i][0]); for(int j = 1; j < MAXL; j++) val[i][j] = Add_Mod(val[i][j - 1], val[i][j - 1]); } Build(1, n, 1); cd = 0; while(m--) { RD(a), RD(b); cd = cd + Query(a, b, 1, n, 1); if(cd > MOD) cd -= MOD; PT(cd); puts(""); } } return 0; }

热门文章