题意

给定 $n$ 个组，每个组 $i$ 有 $k_i$ 个元素，分别为 $c_{i, 1}, c_{i, 2}, \cdots, c_{i, k_i}$。求在每一个组都必须选至少一个元素的情况下是否可以使选出的元素总和恰为 $s$，若可以则给出任意方案。

$1 \le n, s, \sum_{i = 1}^{n} k_i \le 10^5, \sum_{i = 1}^{n} k_i \cdot s \le 10^7$。

第一问

题目的形式非常像分组背包，加上 $\sum_{i = 1}^{n} k_i \cdot s \le 10^7$ 就更使人往背包的方向想了（毕竟这样的条件几乎只有背包会用到）。

具体的，定义状态 $f_{i, j}$ 表示前 $i$ 个组，选出元素和为 $j$ 是否可行。设当前元素的值为 $w$，则有转移：

$f_{i, w + v} \gets f_{i, w + v} \operatorname{or} f_{i - 1, v} \operatorname{or} f_{i, v} (0 \le v \le s - w)$

其实就是经典背包。转移 $f_{i - 1, v}$ 表示这个元素是这个组第一个被选的，$f_{i, v}$ 则相反。初始状态为 $f_{0, 0} = \mathrm{true}$。

第一维要滚动掉。

第二问

有一个直接的想法就是每个状态都开一个 vector，从 $S$ 状态转移到 $T$ 状态的时候就把 $S$ 的 vector 复制一份再加进枚举到的元素。但是无论时间还是空间上都炸到起飞。（我才不告诉你是谁想出来的呢）

当然，如果你仔细思考了上面的做法，就会发现它的瓶颈在于一个状态可能会转移到很多个状态，而这个重复显然是很浪费的。

于是，可以考虑一种类似可持久化线段树的思想，为每个状态都设置一个节点，转移的时候就可以直接让转移到的状态向源状态连边。查询答案时直接遍历答案状态所在的子树即可。

两问总时间、空间复杂度均为 $\Theta(\sum_{i = 1}^{n} k_i \cdot s)$。

实现细节

• 第一问中的 $v$ 要从大到小枚举，否则会变成完全背包（一个元素会被选多次）。
• 可以用 vector 来存各个组中的元素。
• 注意第二问中的“源状态” 也包括元素本身（详见代码一节）。

代码

dp 数组对应 $f$，idsta 数组存储了这个状态的编号，son 就是编号在树上的儿子。

#include <cstring>
#include <iostream>
#include <utility>
#include <vector>
#define MAXN 100003
#define VMAXN 10000003
using namespace std;
using PII = pair<int, int>;

vector<int> prob[MAXN];
PII son[VMAXN];
bool isans[MAXN];
bool dp[2][MAXN];
int szsm, idsta[2][MAXN], vec[MAXN];

void dfs(const int u)
{
    if (u <= szsm)
    {
        isans[u] = true;
        return;
    }
    if (son[u].first)
        dfs(son[u].first);
    if (son[u].second)
        dfs(son[u].second);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int n, s, szcur;
    cin >> n >> s;
    for (int i = 1; i <= n; ++i)
    {
        cin >> szcur;
        szsm += szcur;
        prob[i].resize(szcur);
        for (int j = 0; j < szcur; ++j)
            cin >> prob[i][j];
    }
    int tot = szsm;
    dp[0][0] = true;
    for (int i = 1, o = 1, idv = 0; i <= n; ++i, o ^= 1)
    {
        memset(dp[o], 0, sizeof(dp[o]));
        for (const int j : prob[i])
        {
            ++idv;
            for (int v = s - j; v >= 0; --v)
            {
                if (dp[o][v + j])
                    continue;
                if (dp[o ^ 1][v])
                {
                    dp[o][v + j] = true;
                    son[++tot] = {idv, idsta[o ^ 1][v]};
                    idsta[o][v + j] = tot;
                }
                else if (dp[o][v])
                {
                    dp[o][v + j] = true;
                    son[++tot] = {idv, idsta[o][v]};
                    idsta[o][v + j] = tot;
                }
            }
        }
    }
    if (!dp[n & 1][s])
    {
        cout << "No\n";
        return 0;
    }
    cout << "Yes\n";
    dfs(idsta[n & 1][s]);
    int vecp = 0;
    for (int i = 1, idv = 0; i <= n; ++i)
    {
        vecp = 0;
        for (int j = 1; j <= prob[i].size(); ++j)
        {
            ++idv;
            if (isans[idv])
                vec[++vecp] = j;
        }
        cout << vecp << '\n';
        for (int j = 1; j < vecp; ++j)
            cout << vec[j] << ' ';
        cout << vec[vecp] << '\n';
    }
    return 0;
}