T22:和風いろはちゃん

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）代码

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;                                      // 取模常数

static unsigned long long ne[131075][11];                        // ne[state][v]：状态state加上数字v后的新状态
static int f[41][131075];                                        // f[len][state]：长度len时处于state的方案数（取模）

int main() {
    int n, x, y, z;                                              // n为长度，x,y,z为三段目标和
    scanf("%d%d%d%d", &n, &x, &y, &z);                           // 读入 n, X, Y, Z

    y += x;                                                      // 把y改成X+Y，作为第二段结束的分界点
    z += y;                                                      // 把z改成X+Y+Z，作为总目标

    for (int state = 1; state <= (1 << z); state++) {            // 枚举所有状态（你的代码从1开始）
        for (int v = 1; v <= 10; v++) {                          // 枚举当前位置填入的数字v（1..10）
            unsigned long long ns = 1;                           // ns初始化为1，保证bit0为1（可从当前位置重新开始）

            for (int k = 0; k + v <= z; k++) {                   // 枚举旧状态中可能的累计和k
                if (!(state & (1ULL << k))) continue;            // 如果旧状态没有k，则跳过

                bool crossX = (k < x && k + v > x);              // 判断是否跨越x分界点
                bool crossY = (k < y && k + v > y);              // 判断是否跨越y分界点

                if (crossX) continue;                            // 跨越x不合法
                if (crossY) continue;                            // 跨越y不合法

                ns |= (1ULL << (k + v));                         // 合法则把k+v标记为可达
            }

            if (state == (1 << z) || ns >= (1ULL << z)) {        // 若已经成功或本次达到成功
                ns = (1ULL << z);                                // 压成吸收成功态
            }

            ne[state][v] = ns;                                   // 保存转移
        }
    }

    f[0][1] = 1;                                                 // 初始：长度0时只有bit0为1的状态

    for (int len = 1; len <= n; len++) {                         // 枚举长度len
        for (int state = 1; state <= (1 << z); state++) {        // 枚举上一步状态
            if (f[len - 1][state] == 0) continue;                // 方案数为0就跳过

            for (int v = 1; v <= 10; v++) {                      // 枚举本位填入的数字v
                int nstate = (int)ne[state][v];                  // 得到新状态
                f[len][nstate] += f[len - 1][state];             // 累加方案数
                if (f[len][nstate] >= MOD) f[len][nstate] -= MOD;// 取模（单次加法够用）
            }
        }
    }

    cout << f[n][1 << z];                                        // 输出长度n且成功态的方案数
    return 0;                                                    // 程序结束
}