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)个球的所有方案的得分之和。
这下可把Alice难倒了，于是Alice找到了聪明的你。你能帮帮他嘛？ 由于所有方案的得分之和可能很大，你只需要输出得分之和对1000000007(10^9+7)取模的结果（负数请加上10^9+7变成非负数）即可。
Input Format
输入第一行包含两个正整数n,m，分别表示球的个数和Bob的操作条数。 接下来一行包含n个由空格隔开的整数，表示每个球初始的权值。
接下来m行，每行表示Bob的一个操作。 若该行形如“1 a b c”，则表示Bob将编号属于[a,b]的所有球的权值都加上了c； 若该行形如“2 a b”，则表示Bob将编号属于[a,b]的所有球的权值都置为了其相反数； 若该行形如“3 a b k”，则表示Bob向Alice询问了从[a,b]中选出k个球的所有取球方案的得分之和。
Output Format
对于Bob的每一个询问操作，输出一行，表示该询问的答案。
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
Data Range
对于25%的数据，n≤100, m≤50000； 对于另25%的数据，n≤50000, m≤100； 对于100%的数据，n≤50000, m≤50000, k≤10。 保证所有输入数据的绝对值均不超过10^9，且k≤b-a+1
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 read(){
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};
int add[MAXN] = {0}, add_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];
swap(add[id << 1], add_neg[id << 1]), swap(add[id << 1 | 1], add_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;
}
if (add[id] != 0){
add[id << 1] = modadd(add[id << 1], add[id]);
add[id << 1 | 1] = modadd(add[id << 1 | 1], add[id]);
add_neg[id << 1] = modadd(add_neg[id << 1], add_neg[id]);
add_neg[id << 1 | 1] = modadd(add_neg[id << 1 | 1], add_neg[id]);
modify(id << 1, len, add[id], add_neg[id]);
modify(id << 1 | 1, len, add[id], add_neg[id]);
add[id] = add_neg[id] = 0;
}
}
void update(int id, int l, int r){
if (l > _b || r < _a) return ;
if (l >= _a && r <= _b){
if (opt == 1){
// add
add[id] = modadd(add[id], _v);
int neg_v = takexfs(_v);
add_neg[id] = modadd(add_neg[id], neg_v);
modify(id, (r - l + 1), _v, neg_v);
}else {
// takes minus
swap(add[id], add_neg[id]);
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;
curres.arr[1] = modadd(lres.arr[1], rres.arr[1]);
for (int j = 2; j <= 10; ++j){
curres.arr[j] = modadd(lres.arr[j], rres.arr[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(){
n = read(), m = read();
for (siz = 1; siz < n; siz <<= 1) ;
for (int i = 1; i <= n; ++i){
int a = read();
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--) {
opt = read();
if (opt == 1){
_a = read(), _b = read(), _v = read();
if (_v < 0) _v += M;
update(1, 1, siz);
}
if (opt == 2){
_a = read(), _b = read();
update(1, 1, siz);
}
if (opt == 3){
_a = read(), _b = read(), _v = read();
Q curres = query(1, 1, siz);
printf("%d\n", curres.arr[_v]);
}
}
}
int main(){
init();
solve();
return 0;
}