先上代码：

#define MX 10
#define NX 200
using namespace std;
int a[MX + 10],p[MX + 10][NX + 10];
long long t[1000000 + 10];
int k,M;
long long ans,cnt,b;
int check(int x)
{
    int L = 1,R = cnt,mid;
    while(L < R)
    {
        mid = (L + R) >> 1;
        if (t[mid] > x)
        {
            R = mid;
        }
        else
        {
            L = mid + 1;
        }
    }
    if (t[L] <= x)
    {
        return 0;
    }
    return cnt - L + 1;
}
void dfs1(int n,int sum)
{
    if (n > 3)
    {
        if (sum > M)
        {
            ans += b;
        }
        else
        {
            int q = check(M - sum);
            ans += q;
        }
        return ;
    }
    for (int i = 1;i <= a[n];i++)
    {
        dfs1(n + 1,sum + p[n][i]);
    }
    dfs1(n + 1,sum);
}
void dfs2(int n,int sum)
{
    if (n > k)
    {
        t[++cnt] = sum;
        return ;
    }
    for (int i = 1;i <= a[n];i++)
    {
        dfs2(n + 1,sum + p[n][i]);
    }
    dfs2(n + 1,sum);
}
int main()
{
    while(cin >> k >> M)
    {
        ans = cnt = 0;
        b = 1;
        int i,j;
        for (i = 1;i <= MX;i++)
        {
            a[i] = 0;
            for (j = 1;j <= NX;j++)
            {
                p[i][j] = 0;
            }
        }
        for (i = 1;i <= k;i++)
        {
            cin >> a[i];
            for (j = 1;j <= a[i];j++)
            {
                cin >> p[i][j];
            }
            if (i > 3)
            {
                b *= (a[i] + 1);
            }
        }
        if (k <= 3)
        {
            dfs2(1,0);
            for (i = 1;i <= cnt;i++)
            {
                if (t[i] > M)
                {
                    ans++;
                }
            }
        }
        else
        {
            dfs2(4,0);
            sort(t + 1,t + cnt + 1);
            dfs1(1,0);
        }
        cout << ans << endl;
    }
    return 0;
}

这道题难度不高（大概是黄题左右，CF大概1400）。显然，这道题是DFS，但是很不幸，如果按照传统的DFS函数来写，那么每次分叉的“树枝”个数就是100 + 1 = 101（100表示ai种任选一个的最大值,1表示整个ai一类都不选），而深度是k <= 6。取最大值6,不难发现搜索状态空间的大小远远超出一般DFS算法题目的时间限制(100)^6 = 10^12次。

如果说普通计算机1s能算1e8次，那么10^12就得算将近3个小时。。。。

其他题解（不管是蒟蒻还是大佬们）的大佬们一般都是用的DFS+剪枝，这确实难度不高，很容易写。虽然剪枝确实能够大量减少状态空间，但是不能对时间复杂度的降低有任何贡献（换句话说，你一旦碰上了刁钻的数据，容易暴毙；甚至是被卡常爆零qwq。。。）。

本人蒟蒻提供一种个人感觉很不错的算法（一种新颖的分治搜索）：

首先，我们将k分解成3 + (k - 3)，那么在k > 3时，我们就可以先对后3个种类物品进行搜索，用一个t[]来存储对后三种物品搜索后好感度之和（这大概是100^3 = 1e6次，对计算机来说很轻松）。然后再对t[]进行从小到大排序（为了使得t[]具有单调性，以保证后续二分查找的有效性）。

然后，我们再对前三种物品进行搜索（效率同上），搜索途中(已经搜索过了了3种物品)可以剪枝（比如说当当前选中物品的好感度之和已经>M,满足条件，那么就可以用ans += a[4] * a[5] * a[6]，不过要注意的是，a[5],a[6]可能是0,所以建议最好在读入时就用b记录下）。搜索最后，我们可以二分查找M - sum,找到在t[]中第一个>M - sum的位置，那么此时该位置包括该位置后面的数+sum就一定>M满足条件了,所以二分查找check()函数的返回值就是当前sum加上后三种物品后的可行解的个数！最后累加到ans输出即可。

要注意的是，二分查找每个人有每个人喜欢的写法，这里我不多BB了。

PS：还有一种非常高妙的搜索算法(分治+分块+二分+DFS+模拟+双指针(+快速幂))，速度极快，题目中k <= 6若改为k <= 10,估计大部分人的代码都卡掉了(包括上述我提供的代码),但是这种“神奇”的算法却不会。这里献上：

#include <bits/stdc++.h>
#define MX 10
#define NX 100
#define SEX 10000
using namespace std;
int k,M;
int a[MX + 10][NX + 10];
void dfs(int s,int e,vector<long long> &v,long long sum) 
{
    if (s > e)
	{
		v.push_back(sum); 
		return;
	}  
    dfs(s + 1,e,v,sum);
    for (int i = 1;i <= a[s][0];i++)
	{
		dfs(s + 1,e,v,sum + a[s][i]);
	} 
}
long long fun(vector<long long> &m,vector<long long> &t, long long R) 
{
    long long cnt = 0;
    int j = t.size() - 1;
    for (int i = 0;i < m.size();i += SEX) 
	{
		int len = (int)(m.size());
        int end = min(len,i + SEX);
        while (j >= 0 && m[i] + t[j] > R) 
		{
			j--;
		}
        for (int k = i;k < end;k++) 
		{
            while (j >= 0 && m[k] + t[j] > R) 
			{
				j--;
			}
            cnt += t.size() - j - 1;
        }
    }
    return cnt;
}
long long solve() 
{
    vector<long long> front,mid,tail;
    int sp1 = min(3,k);
    dfs(1,sp1,front,0);
    if (k > 3) 
	{
        int sp2 = min(6,k);
        dfs(4,sp2,mid,0);
        if (k > 6) 
		{
			dfs(7,k,tail,0);
		}
    }
    sort(mid.begin(),mid.end());
    sort(tail.begin(),tail.end());
    long long ans = 0;
    for (int i = 0;i < front.size();i++)
	{
		long long q = front[i];
        long long r = M - q;
        if (k <= 3) 
		{
			ans += (q > M);
		}
        else if (k <= 6) 
		{
            ans += mid.end() - upper_bound(mid.begin(),mid.end(),r);
        } 
		else 
		{
            ans += fun(mid,tail,r);
        }
    }
    return ans;
}
int main() 
{
	int i,j;
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    while (cin >> k >> M) 
	{
        for (i = 1;i <= k;i++)
	 	{
            cin >> a[i][0];
            for (j = 1;j <= a[i][0];j++)
            {
            	cin >> a[i][j];
			}
        }
        cout << solve() << '\n';
    }
    return 0;
}

该代码配上快速幂和位运算效率（上面没搭配）可以缩小到约为6e7（k == 9,ai均为1000时）.过于神奇就不多说了。没准可以拿个专利什么的，呵呵呵，给我高兴一下午。。。。