题解 | #美丽的项链#

知识点：分组背包，01背包 一共有n组，每组有物品的体积为l到r的物品，且每组物品有个r - l + 1个。对于一组中的某个物品，我们只能选和不选，则满足01背包条件。每个组只能由上一组的状态转移而来，符合题中n个组都选。定义状态 dp[i][j] 为 1~i 组中，体积为 j 的方案数，转移公式为 dp[i][j] += dp[i - 1][j - v]。

using namespace std;
#define int long long
const int mod = 1e9 + 7, N = 1e3 + 10;
int f[25][105];
signed main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, m; cin >> n >> m;
	f[0][0] = 1;
	for(int i = 1; i <= n; i ++)
	{
		int l, r; cin >> l >> r;
		for(int j = 0; j <= m; j ++)
		{
			for(int k = l; k <= r; k ++)
			{
				if(j >= k) f[i][j] += f[i - 1][j - k];
			}
		}
	}
	cout << f[n][m] << '\n';
}