# 14124: 【原4124】选球游戏

### 题目描述

author: Ca. 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4124

## Description

Alice和Bob在玩游戏。在他们面前有n个球排成一排，从左到右按1到n编号。每个球有一个可正可负的权值。每一轮，Bob会选定一个区间[a,b]，将编号在这个区间内的所有球的权值加上一个值c，或者将编号在这个区间内的所有球的权值都设为其相反数。Alice则需从这n个球中选出k个球来，他的得分为这k个球的权值的乘积。

Alice每次都能快快地找出得分最优的选球方案来。Bob想了想，决定提升游戏难度。他每次会选定一个区间[a,b]，然后询问Alice在这个区间内选出(1≤k≤10)个球的所有方案的得分之和。

## Sample Input

``````10 9
3 6 7 4 6 1 6 7 2 6
3 5 7 3
1 1 7 -9
1 2 3 5
3 2 6 1
2 5 8
3 5 7 3
2 2 3
3 1 10 2
3 1 2 2
``````

## Sample Output

``````36
999999996
72
999999885
12
``````

## zqy2018's solution

``````/*
See the solution at https://github.com/zqy1018/sjtu_oj_solutions/blob/master/solutions/sjtu4124.md
*/
#include <bits/stdc++.h>
#define INF 2000000000
#define MAXN 131100
#define M 1000000007
using namespace std;
typedef long long ll;
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
struct Q{
int arr[11];
Q(){
for (int i = 1; i <= 10; ++i)
arr[i] = 0;
}
};
int n, m, siz;
int fac[MAXN], inv[MAXN], invfac[MAXN];
int logg[MAXN] = {0};
int CC[MAXN][11] = {0}, tmp[11];
bool xfs[MAXN] = {0}, xfs_neg[MAXN] = {0};
Q res[MAXN], res_neg[MAXN];
int _a, _b, _v, opt;

inline int modadd(int x, int y){
return (x + y >= M ? x + y - M: x + y);
}
inline int takexfs(int x){
return (x == 0 ? 0: M - x);
}
inline int C(int n, int m){
return 1ll * (1ll * fac[n] * invfac[m] % M) * invfac[n - m] % M;
}

void maintain(int i){
for (int j = 1; j <= 10; ++j){
res[i].arr[j] = modadd(res[i << 1].arr[j], res[i << 1 | 1].arr[j]);
res_neg[i].arr[j] = modadd(res_neg[i << 1].arr[j], res_neg[i << 1 | 1].arr[j]);
for (int t = 1; t < j; ++t)
res[i].arr[j] = modadd(1ll * res[i << 1].arr[t] * res[i << 1 | 1].arr[j - t] % M, res[i].arr[j]),
res_neg[i].arr[j] = modadd(1ll * res_neg[i << 1].arr[t] * res_neg[i << 1 | 1].arr[j - t] % M, res_neg[i].arr[j]);
}
}
void modify(int id, int len, int x, int x_neg){
for (int i = 1; i <= 10; ++i)
tmp[i] = res[id].arr[i];
tmp[0] = 1;
for (int i = 1; i <= 10; ++i){
int fin_res = 0;
for (int j = 0, xx = 1; j <= i; ++j, xx = 1ll * xx * x % M)
fin_res = modadd(fin_res, 1ll * (1ll * xx * tmp[i - j] % M) * CC[len - i + j][j] % M);
res[id].arr[i] = fin_res;
}

for (int i = 1; i <= 10; ++i)
tmp[i] = res_neg[id].arr[i];
tmp[0] = 1;
for (int i = 1; i <= 10; ++i){
int fin_res = 0;
for (int j = 0, xx = 1; j <= i; ++j, xx = 1ll * xx * x_neg % M)
fin_res = modadd(fin_res, 1ll * (1ll * xx * tmp[i - j] % M) * CC[len - i + j][j] % M);
res_neg[id].arr[i] = fin_res;
}
}
void pushdown(int id, int len){
if (xfs[id]){
xfs[id << 1] = !xfs[id << 1], xfs[id << 1 | 1] = !xfs[id << 1 | 1];
xfs_neg[id << 1] = !xfs_neg[id << 1], xfs_neg[id << 1 | 1] = !xfs_neg[id << 1 | 1];
for (int i = 1; i <= 10; ++i)
swap(res[id << 1].arr[i], res_neg[id << 1].arr[i]),
swap(res[id << 1 | 1].arr[i], res_neg[id << 1 | 1].arr[i]);
xfs[id] = false;
}
}
}
void update(int id, int l, int r){
if (l > _b || r < _a) return ;
if (l >= _a && r <= _b){
if (opt == 1){
int neg_v = takexfs(_v);
modify(id, (r - l + 1), _v, neg_v);
}else {
// takes minus
xfs[id] = !xfs[id];
xfs_neg[id] = !xfs_neg[id];
for (int i = 1; i <= 10; ++i)
swap(res[id].arr[i], res_neg[id].arr[i]);
}
return ;
}
int mid = (l + r) >> 1;
pushdown(id, mid - l + 1);
if (_a <= mid) update(id << 1, l, mid);
if (_b > mid) update(id << 1 | 1, mid + 1, r);
maintain(id);
}
Q query(int id, int l, int r){
if (l > _b || r < _a) return Q();
if (l >= _a && r <= _b) return res[id];
int mid = (l + r) >> 1;
pushdown(id, mid - l + 1);
if (_b <= mid) return query(id << 1, l, mid);
if (_a > mid) return query(id << 1 | 1, mid + 1, r);
Q lres = query(id << 1, l, mid), rres = query(id << 1 | 1, mid + 1, r);
Q curres;
for (int j = 2; j <= 10; ++j){
for (int t = 1; t < j; ++t)
curres.arr[j] = modadd(1ll * lres.arr[t] * rres.arr[j - t] % M, curres.arr[j]);
}
return curres;
}
void init(){
for (siz = 1; siz < n; siz <<= 1) ;
for (int i = 1; i <= n; ++i){
if (a < 0) a += M;
res[i + siz - 1].arr[1] = a;
res_neg[i + siz - 1].arr[1] = takexfs(a);
}
for (int i = siz - 1; i >= 1; --i)
maintain(i);

// build C
fac[1] = inv[1] = invfac[1] = 1;
fac[0] = invfac[0] = 1;
for (int i = 2; i <= siz; ++i)
inv[i] = 1ll * (M - M / i) * inv[M % i] % M,
fac[i] = 1ll * fac[i - 1] * i % M,
invfac[i] = 1ll * invfac[i - 1] * inv[i] % M;
CC[0][0] = 1;
for (int i = 1, j = 1; i <= siz; i <<= 1, ++j){
logg[i] = j;
for (int u = i; u >= i - 10 && u > 0; --u)
for (int t = min(10, u); t >= 0; --t)
CC[u][t] = C(u, t);
}
}
void solve(){
while (m--) {
if (opt == 1){
if (_v < 0) _v += M;
update(1, 1, siz);
}
if (opt == 2){
update(1, 1, siz);
}
if (opt == 3){