三维前缀和

二维前缀和是一维前缀和的扩展，三维前缀和则是二维的基础上再加一维

三维前缀和

求三维前缀和数组，可以分别对 x，y，z 维进行求和。二维同样也可以分别对 x，y 维进行求和，只是我们很少这样去做。

具体来说 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
for(int k=1; k<=h; k++)
mat[i][j][k] += mat[i-1][j][k];

for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
for(int k=1; k<=h; k++)
mat[i][j][k] += mat[i][j-1][k];

for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
for(int k=1; k<=h; k++)
mat[i][j][k] += mat[i][j][k-1];

还有一种容斥的方法也可以求这个，不过比较复杂 :

1
2
3
4
5
6
7
8
9
10
11
12
sum[i][j][k] = 
    +a[i][j][k]

    +sum[i-1][j][k]
    +sum[i][j-1][k]
    +sum[i][j][k-1]

    -sum[i-1][j-1][k]
    -sum[i-1][j][k-1]
    -sum[i][j-1][k-1]

    +sum[i-1][j-1][k-1]

求子三维数组的和

求 [x1, x2] × [y1, y2] × [z1, z2] 这个矩形题的和，需要用到容斥定理，可以画图去理解。

1
2
3
4
5
6
7
8
9
10
11
12
sum[x1...x2][y1...y2][z1...z2] =
    +sum[x2][y2][z2]

    -sum[x1-1][y2][z2]
    -sum[x2][y1-1][z2]
    -sum[x2][y2][z1-1]

    +sum[x1-1][y1-1][z2]
    +sum[x1-1][y2][z1-1]
    +sum[x2][y1-1][z1-1]

    -sum[x1-1][y1-1][z1-1]

B-Chengdu ICPC 2024

题意 :

有 3 种服装，同种服装完全相同，要将这 3 种服装分配给 n 个人，有些人已有服装无需分配，且要求相邻两个人的服装不能相同。每次询问给定 3 种服装数量 x，y，z，问有多少种分配方式？

(0 ≤ x, y, z ≤ 300, n ≤ 300, Q ≤ 1e5)

解析 :

因为 x，y，z 比较小，我们可以直接预处理出来所有 x，y，z 的情况数，这个 dp 很好去求。

定义 dp[x][y][z] -> 3 种服装恰好用了 x, y, z 套。然后简单转移一下就好。

方案数则为三维前缀和 ∑dpi ≤ x, j ≤ y, k ≤ z

MYCODE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int inf = 0x3f3f3f3f;
const int mo = 1e9 + 7;
const int MX = 301;

ll dp[MX][MX][MX][3];
ll f[MX][MX][MX];
int inv2 = (mo + 1) / 2;

void add(auto& x, auto y){
    x = (x + y) % mo;
}

void solve(){
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    s = "x" + s;

    dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 1;
    for(int i=0; i<=300; i++)
    for(int j=0; j<=300; j++)
    for(int k=0; k<=300; k++)
    for(int o=0; o<3; o++){
        int pos = i + j + k;
        if(pos > n) continue;
        if(o != 0 && i && (s[pos]=='?' || s[pos]=='a')) add(dp[i][j][k][0], dp[i-1][j][k][o]);
        if(o != 1 && j && (s[pos]=='?' || s[pos]=='b')) add(dp[i][j][k][1], dp[i][j-1][k][o]);
        if(o != 2 && k && (s[pos]=='?' || s[pos]=='c')) add(dp[i][j][k][2], dp[i][j][k-1][o]);
    }

    int na = count(s.begin(), s.end(), 'a');
    int nb = count(s.begin(), s.end(), 'b');
    int nc = count(s.begin(), s.end(), 'c');

    for(int i=na; i<=300; i++)
    for(int j=nb; j<=300; j++)
    for(int k=nc; k<=300; k++)
    for(int o=0; o<3; o++) if(i + j + k == n){
        f[i-na][j-nb][k-nc] += dp[i][j][k][o];
    }

    for(int j=0; j<=300; j++)
    for(int k=0; k<=300; k++)
    for(int i=1; i<=300; i++)
    add(f[i][j][k], f[i-1][j][k]);

    for(int i=0; i<=300; i++)
    for(int k=0; k<=300; k++)
    for(int j=1; j<=300; j++)
    add(f[i][j][k], f[i][j-1][k]);

    for(int i=0; i<=300; i++)
    for(int j=0; j<=300; j++)
    for(int k=1; k<=300; k++)
    add(f[i][j][k], f[i][j][k-1]);

    for(int i=0; i<q; i++){
        int x, y, z;
        cin >> x >> y >> z;
        cout << f[x][y][z]*inv2%mo << '\n';
    }

}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1; // cin >> t;
    while(t--) solve();
    
    return 0;
}

题目链接 : B - Chengdu ICPC 2024