第1行：两个整数 N (1 ≤ N ≤ 2 × 103) 和 M (1 ≤ M ≤ 2 × 103)，物品的数量和最大的容积。
第2行： N 个整数 W1, W2, ..., WN, 物品的体积。
一个 N × M 的矩阵， Count(i, x)的末位数字
。。。我也不知道我是怎么想到的，只记得一开始我打了个O（n2mlogn）的代码交上后比暴力还慢。。。。
由此想到：合并背包的复杂度为n2，所以与其合并背包还不如一个一个地添加元素，由此可以想到：我们
考虑每个物品对复杂度的贡献,期望为mlogn，那么是不是可以用分治？so：假如我们有一棵线段树，在
线段树的每一层对每一个物品跑背包，保证每个物品的贡献，so：我们还是考虑线段树：在线段树的
每一个结点开一个背包，怎么用呢？考虑每个物品对答案的贡献，对线段树的没个非叶子节点：
假设某个节点控制范围为l到r，则mid=l+r>>1;（废话）那么（l，mid）范围内所有的点会对（mid+1，r）
的答案作出贡献，所以把（l，mid）内每个物品单独取出，加入到rc的背包中，并且在考虑以rc为根的子树时
把rc的背包下传以传递贡献，下传时直接memcpy即可;在叶子节点统计答案，直接输出
1 #include <bits/stdc++.h>
2 #define N 2003
3 #define reg register
4 using namespace std;
5 int n, m;
6 int w[N];
7 int pos[N];
8 int f[N << 2][N];
9 void ask(const int g, const int l, const int r) {
10 if (l == r) {
11 pos[l] = g;
12 return;
13 }
14 const int mid = l + r >> 1, lc = g << 1, rc = g << 1 | 1;
15 f[lc][0] = f[rc][0] = 1;
16 for (int i = 1; i <= m; ++i) f[lc][i] = f[rc][i] = f[g][i];
17 for (reg int i = mid + 1; i <= r; ++i) {
18 for (reg int j = m; j >= w[i]; --j) {
19 f[lc][j] += f[lc][j - w[i]];
20 f[lc][j] = f[lc][j] >= 10 ? f[lc][j] - 10 : f[lc][j];
21 }
22 }
23 for (reg int i = l; i <= mid; ++i) {
24 for (reg int j = m; j >= w[i]; --j) {
25 f[rc][j] += f[rc][j - w[i]];
26 f[rc][j] = f[rc][j] >= 10 ? f[rc][j] - 10 : f[rc][j];
27 }
28 }
29 ask(lc, l, mid);
30 ask(rc, mid + 1, r);
31 }
32 int main() {
33 scanf("%d%d", &n, &m);
34 for (reg int i = 1; i <= n; ++i) scanf("%d", &w[i]);
35 ask(1, 1, n);
36 for (reg int i = 1; i <= n; ++i) {
37 for (reg int j = 1; j <= m; ++j) putchar(f[pos[i]][j] + 48);
38 puts("");
39 }
40 }
感谢loj码风优化（貌似某位压行大神也写过？）优化：
1.其实不必在所有节点开背包，在每层开一个即可;
2.到达叶子节点可直接输出答案，不必最后统计输出;
View Code