10.24 Updata
考场上写出来了233333
#include <iostream> #include <cstdio> #define rg register #define Max 100005 inline void read (int &n) { rg char c = getchar (); bool temp = false; for (n = 0; !isdigit (c); c = getchar ()) if (c == '-') temp = true; for (; isdigit (c); n = n * 10 + c - '0', c = getchar ()); if (temp) n = -n; } typedef long long LL; int a[Max]; LL C[Max][11]; #define mo 1000000007 struct SD { SD *L, *R; int l, r, m; LL f[11], t1; bool t2; void D (); void U (); } *null = new SD, pool[Max << 2], *Ta = pool; inline LL Inc (LL &x, LL y) { for (x += y; x >= mo; x -= mo); } void Updata (SD *&n, int l, int r, int c) { rg int Len = r - l + 1, i, j; static LL _f[11]; LL t, p; for (i = 0; i <= 10; ++ i) _f[i] = n->f[i]; for (i = 1; i <= 10; ++ i) for (t = 1, j = n->f[i] = 0; j <= i; ++ j) { p = _f[i - j] * C[Len - i + j][j] % mo * t % mo; Inc (n->f[i], p), t = t * c % mo; } } void SD :: D () { if (t1) { if (L->t2) L->t1 = (L->t1 + mo - t1) % mo; else L->t1 = (L->t1 + t1) % mo; if (R->t2) R->t1 = (R->t1 + mo - t1) % mo; else R->t1 = (R->t1 + t1) % mo; Updata (L, l, m, t1), Updata (R, m + 1, r, t1); t1 = 0; } if (t2) { L->t2 ^= 1, R->t2 ^= 1; rg int i; t2 = false; for (i = 1; i <= 10; i += 2) L->f[i] = mo - L->f[i], R->f[i] = mo - R->f[i]; } } void SD :: U () { f[0] = 1; rg int i, j; for (i = 1; i <= 10; ++ i) for (j = f[i] = 0; j <= i; ++ j) Inc (f[i], L->f[j] * R->f[i - j] % mo); } class SegmentTree { private : SD *Root, *Limit; SD *New (int x, int y) { ++ Ta, Ta->l = x, Ta->r = y, Ta->m = x + y >> 1; for (rg int i = 0; i <= 10; ++ i) Ta->f[i] = 0; Ta->L = null, Ta->R = null, Ta->t1 = Ta->t2 = 0; return Ta; } SD *Q (SD *&n, int l, int r) { if (l <= n->l && n->r <= r) return n; n->D (); SD *p = ++ Ta; p->L = p->R = null; if (r <= n->m) return Q (n->L, l, r); if (l > n->m) return Q (n->R, l, r); p->L = Q (n->L, l, r), p->R = Q (n->R, l, r); return p->U (), p; } void Modi1 (SD *&n, int l, int r, int c) { if (l <= n->l && n->r <= r) { if (n->t2) n->t1 = (n->t1 + mo - c) % mo; else Inc (n->t1, c); Updata (n, n->l, n->r, c); return ; } n->D (); if (l <= n->m) Modi1 (n->L, l, r, c); if (r > n->m) Modi1 (n->R, l, r, c); n->U (); } void Build (SD *&n, int l, int r) { n = New (l, r); if (l == r) { n->f[0] = 1, n->f[1] = (a[l] % mo + mo) % mo; return ; } Build (n->L, l, n->m), Build (n->R, n->m + 1, r), n->U (); } void Modi2 (SD *&n, int l, int r) { if (l <= n->l && n->r <= r) { for (rg int i = 1; i <= 10; i += 2) n->f[i] = mo - n->f[i]; n->t2 ^= 1; return ; } n->D (); if (l <= n->m) Modi2 (n->L, l, r); if (r > n->m) Modi2 (n->R, l, r); n->U (); } public : void Build (int l, int r) { Build (Root, l, r); Limit = ++ Ta; return ;} int Q (int l, int r, int k) { SD *c = Q (Root, l, r); return Ta = Limit, c->f[k] % mo; } void Modi1 (int l, int r, int c) { Modi1 (Root, l, r, c); return ; } void Modi2 (int l, int r) { Modi2 (Root, l, r); return ; } } T; std :: string Name = "game", _I = ".in", _O = ".out"; int main (int argc, char *argv[]) { freopen ((Name + _I).c_str (), "r", stdin); freopen ((Name + _O).c_str (), "w", stdout); int N, M, t, x, y, z; read (N), read (M); rg int i, j; null->L = null->R = null; null->l = null->r = null->t1 = null->t2 = null->m = 0; for (i = 0; i <= 10; ++ i) null->f[i] = 0; for (i = C[0][0] = 1; i <= N; ++ i) for (C[i][0] = j = 1; j <= 10; ++ j) C[i][j] += C[i - 1][j - 1] + C[i - 1][j], C[i][j] %= mo; for (i = 1; i <= N; ++ i) read (a[i]); for (T.Build (1, N), i = 1; i <= M; ++ i) { read (t), read (x), read (y); if (t == 1) { read (z), z = (z % mo + mo) % mo, T.Modi1 (x, y, z); } else if (t == 2) T.Modi2 (x, y); else read (z), printf ("%d ", T.Q (x, y, z)); } return 0; }
/* 莫Copy 还未调出来 */ #define DEBUG for (int q = 0; q <= 10; ++ q) std :: cout << n->f[q] << " "; puts (""); #include <iostream> #include <cstdio> #define rg register #define Max 100005 inline void read (int &n) { rg char c = getchar (); bool temp = false; for (n = 0; !isdigit (c); c = getchar ()) if (c == '-') temp = true; for (; isdigit (c); n = n * 10 + c - '0', c = getchar ()); if (temp) n = -n; } typedef long long LL; int a[Max]; LL C[Max][11]; #define mo 1000000007 struct SD { SD *L, *R; int l, r, m; LL f[11], t1; bool t2; void D (); void U (); } *null = new SD, pool[Max << 2], *Ta = pool; inline LL Inc (LL &x, LL y) { for (x += y; x >= mo; x -= mo); } void Updata (SD *&n, int l, int r, int c) { rg int Len = r - l + 1, i, j; static LL _f[11]; LL t, p; for (i = 0; i <= 10; ++ i) _f[i] = n->f[i]; for (i = 1; i <= 10; ++ i) for (t = 1, j = n->f[i] = 0; j <= i; ++ j) { p = _f[i - j] * C[Len - i + j][j] % mo * t % mo; Inc (n->f[i], p), t = t * c % mo; } } void SD :: D () { if (t1) { if (L->t2) L->t1 = (L->t1 + mo - t1) % mo; else L->t1 = (L->t1 + t1) % mo; if (R->t2) R->t1 = (R->t1 + mo - t1) % mo; else R->t1 = (R->t1 + t1) % mo; Updata (L, l, m, t1), Updata (R, m + 1, r, t1); t1 = 0; } if (t2) { L->t2 ^= 1, R->t2 ^= 1; rg int i; t2 = false; for (i = 1; i <= 10; ++ i) L->f[i] = mo - L->f[i], R->f[i] = mo - R->f[i]; } } void SD :: U () { f[0] = 1; rg int i, j; for (i = 1; i <= 10; ++ i) for (j = f[i] = 0; j <= i; ++ j) Inc (f[i], L->f[j] * R->f[i - j] % mo); } class SegmentTree { private : SD *Root, *Limit; SD *New (int x, int y) { ++ Ta, Ta->l = x, Ta->r = y, Ta->m = x + y >> 1; for (rg int i = 0; i <= 10; ++ i) Ta->f[i] = 0; Ta->L = null, Ta->R = null, Ta->t1 = Ta->t2 = 0; return Ta; } void Build (SD *&n, int l, int r) { n = New (l, r); if (l == r) { n->f[0] = 1, n->f[1] = (a[l] % mo + mo) % mo; return ; } Build (n->L, l, n->m), Build (n->R, n->m + 1, r), n->U (); } SD *Q (SD *&n, int l, int r) { if (l <= n->l && n->r <= r) return n; n->D (); SD *p = ++ Ta; p->L = p->R = null; if (r <= n->m) return Q (n->L, l, r); if (l > n->m) return Q (n->R, l, r); p->L = Q (n->L, l, r), p->R = Q (n->R, l, r); return p->U (), p; } void Modi1 (SD *&n, int l, int r, int c) { if (l <= n->l && n->r <= r) { if (n->t2) n->t1 = (n->t1 + mo - c) % mo; else Inc (n->t1, c); Updata (n, n->l, n->r, c); return ; } n->D (); if (l <= n->m) Modi1 (n->L, l, r, c); if (r > n->m) Modi1 (n->R, l, r, c); n->U (); } void Modi2 (SD *&n, int l, int r) { if (l <= n->l && n->r <= r) { for (rg int i = 1; i <= 10; i += 2) n->f[i] = mo - n->f[i]; n->t2 ^= 1; return ; } n->D (); if (l <= n->m) Modi2 (n->L, l, r); if (r > n->m) Modi2 (n->R, l, r); n->U (); } public : void Build (int l, int r) { Build (Root, l, r); Limit = ++ Ta; return ;} int Q (int l, int r, int k) { SD *c = Q (Root, l, r); return Ta = Limit, c->f[k] % mo; } void Modi1 (int l, int r, int c) { Modi1 (Root, l, r, c); return ; } void Modi2 (int l, int r) { Modi2 (Root, l, r); return ; } } T; std :: string Name = "game", _I = ".in", _O = ".out"; int main (int argc, char *argv[]) { freopen ((Name + _I).c_str (), "r", stdin); freopen ((Name + _O).c_str (), "w", stdout); int N, M, t, x, y, z; read (N), read (M); rg int i, j; null->L = null->R = null; null->l = null->r = null->t1 = null->t2 = null->m = 0; for (i = 0; i <= 10; ++ i) null->f[i] = 0; for (i = C[0][0] = 1; i <= N; ++ i) for (C[i][0] = j = 1; j <= 10; ++ j) C[i][j] += C[i - 1][j - 1] + C[i - 1][j], C[i][j] %= mo; for (i = 1; i <= N; ++ i) read (a[i]); for (T.Build (1, N), i = 1; i <= M; ++ i) { read (t), read (x), read (y); if (t == 1) { read (z), z = (z % mo + mo) % mo, T.Modi1 (x, y, z); } else if (t == 2) T.Modi2 (x, y); else read (z), printf ("%d ", T.Q (x, y, z)); } return 0; }