1)题目意思
长度为 n 的数列,每个数都在 1..10。问有多少个数列满足:存在四个下标 0≤x<y<z<w≤n,使得三段连续区间的和分别等于给定的 X、Y、Z。答案对 1e9+7 取模。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2)思路解析(对应你这份正确代码的做法)
(1)把三段和改成“前缀和分界点”
你代码里先做了:
* y += x,让 y 变成 X+Y
* z += y,让 z 变成 X+Y+Z
也就是说,最终我们要找的是:某个连续区间的“段内前缀和”能否到达:
* x(第一段结束)
* y(第二段结束)
* z(第三段结束,总目标)
(2)状态是什么:用 BITMASK 存“当前能到达的段内前缀和”
你用一个状态 i(bitmask)表示:以某个起点开始往右延伸时,当前这段里可能出现哪些“累计和”。
* bit k 为 1:表示存在一种起点选择,使得从起点到当前位置的累计和为 k
* 特别地,bit0(也就是最低位)一直保持为 1(你用 ne[i][j]=1 保证),表示“可以在当前位置重新开始一段”(相当于随时允许换起点)
(3)转移怎么做:加入一个新数 J(1..10)
从旧状态 i 加入新数字 j 后,新状态 ne[i][j] 的构造逻辑是:
* 对旧状态里每个可达的累计和 k(也就是 i 的 bit k 为 1):
* 新累计和会变成 k+j
* 但不能“跨越边界”:
* 不能出现 k < x 且 k+j > x(跨过 x)
* 不能出现 k < y 且 k+j > y(跨过 y)
* 如果不跨越,就把 k+j 这个位置设为 1
再加上 bit0 恒为 1,所以起点随时可重置。
(4)成功状态(吸收态)
如果已经达到 z(也就是 bit z 为 1),那说明已经找到满足 XYZ 的三段结构。你把它统一压成 1<<z 作为吸收成功态:
* if(i==(1<<z) || ne[i][j] >= (1<<z)) ne[i][j] = 1<<z;
之后不论再加什么数都保持成功态。
(5)DP 计数
f[t][state] 表示长度为 t 的前缀,处于 state 的方案数。
* 初始:f[0][1]=1(只有 bit0 为 1)
* 转移:枚举下一个数 k=1..10
* f[i][ne[j][k]] += f[i-1][j]
最后输出:
* f[n][1<<z](长度为 n 且已经成功的方案数)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3)代码