题解：P17730 [SCP-J 2026] 数组 / array
osmium_dust
·
·
题解
出题人题解。
12pts 1~3
暴力模拟每个 a 数组即可。
40pts 1~7 + 19~21
### 12pts 8\~10
暴力修改暴力查，或者写个线段树，$O(n(p+q))$ 能过。
### 8pts 11\~12
注意到每个询问可以被拆成两个 $a_{i,j}$ 的查询。
$O(n^2)$ 预处理后 $O(1)$ 查询即可。
## 8pts 17\~18
考虑 $a_{i,l}$ 对 $a_{i+j,l+k}$ 的贡献，设这个值是 $s_{j,k}$，易得 $s_{0,0}=1,s_{j,k}=s_{j-1,k}+s_{j,k-1}$ 原因是 $a_{i,j}=a_{i-1,j}+a_{i,j-1}$。到这里整个题就做出来一半了。
修改时暴力修改，查询时暴力查询即可。
## 8pts 15\~16
- 考虑每次修改暴力维护 $a_0$ 数组。设修改 $a_{i+j,l+k}$ 会对 $a_{i,l}$ 造成 $s_{j,k}$ 的贡献，~~这不是二项式反演吗，原谅我出这个题的时候没学到这。~~我们进行简单思考，发现此时有 $s_{0,0}=0$，$s_{j,k}=s_{j+1,k}-s_{j+1,k-1}$。这不就是杨辉三角左对齐之后偶数列变成负数吗？或者预处理出来 $s$，对于每个修改，暴力维护 $a_0$ 即可。
把以上两种做法拼起来，就可以进行修改的时候暴力改 $a_0$，然后查询暴力查即可获得 $100pts$。
## 8pts 13\~14
对第二种做法的启发性部分分。
- 我们考虑把在这个询问前的修改都记下来，然后考虑每个修改对查询造成什么贡献。每个查询是两个单点修改。然后我们可以在 $O(p)$ 时间内回答这一个询问。
- 操作分块一下，块结束之后暴力还原 $a_0$，直接做到 $O(\frac{(p+q)}{B}n^2+B(q+p))$，由基本不等式发现 $B=n$ 时取得最优，为 $O((p+q)n)$。
顺带一提，据说有验题人用这个方法解的。
#### tips
1.注意开 `long long`。
2.各种下标减来减去别减不明白。
给这么多具有启发性和暴力部分分是不是很好（bushi）。
写在后面。当时我以为自己发明了一种新算法，就是把一定的修改分组，等到一定时候重构，结果一看好多人已经发明过了。叫什么操作分块 / 根号重构。[空悲切](https://www.luogu.com.cn/record/282236871)。
附一份正常做法的代码吧。
:::info[Code]
```c++
#define _CRT_SECURE_NO_WARNINGS
#include<bitset>
#include<vector>
#include<string>
#include<iostream>
#include<queue>
#include<stack>
#include <cassert>
#include <cstring>
#include <string>
using namespace std;
/**/
#define int long long
/**/
using ll = long long;
const int MXN = 350;
const int P = 1e9 + 7;
int C[MXN][MXN],q[MXN][MXN];
int n, q1, q2;
int A0[MXN];
void init() {
for (int i = 0; i <= n; i++) {
q[0][i] =q[i][0]= 1;
}
for(int i=1;i<=n;i++)
for (int j = 1; j <= n; j++) {
q[i][j] = q[i][j - 1] + q[i - 1][j];
q[i][j] %= P;
}
C[0][1] = 1;
for(int i=1;i<=n;i++)
for (int j = 1; j <= n; j++) {
C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
C[i][j] %= P;
}
}
int o, x, l, r, k;
void mer(int _x, int v, int p) {
for (int i = 0; i + p <= n; i++) {
A0[i + p] += 1LL * v * C[_x][i+1] * ((i&1) ? -1 : 1);
A0[i + p] %= P;
A0[i + p] += P;
A0[i + p] %= P;
}
}
int que(int _x, int p) {
int c = 0, ans = 0;
for (int i = p; i >= 1; i--) {
ans += 1LL * A0[i] * q[_x - 1][c++];
ans %= P;
}
return ans;
}
void solve() {
cin >> n >> q1 >> q2;
init();
for (int i = 1; i <= n; i++)cin >> A0[i];
int qs = q1 + q2;
while (qs--) {
cin >> o >> x >> l >> r;
if (o == 1) {
cin >> k;
if (x) {
mer(x - 1, k, l);
mer(x - 1, -k, r + 1);
}
else
for (int i = l; i <= r; i++)
A0[i] += k, A0[i] %= P, A0[i] += P, A0[i] %= P;
}
else {
cout << ((que(x+1,r)-que(x+1,l-1))%P+P)%P<<'\n';
}
}
}
signed main() {
string i_ = ".in";
int T;
/*/
cin>>T;
/*/
T = 1;
/**/
while (T--) {
solve();
}
return 0;
}
```
:::