题目

代码：

#include <iostream>
#include <vector>
using namespace std;
const int MOD=1e9+7;
int main(){
	int n,m;
	cin >> n >> m;
	vector<pair<int,int>> a(n);
	for (int i=0;i<n;++i){
		scanf("%d%d",&a[i].first,&a[i].second);
	}
	vector<vector<int>> dp(n,vector<int>(m+1,0));
	for (int i=0;i<n;++i){
		if (i==0){
			for (int j=1;j<=a[i].second && a[i].first*j<=m;++j){
				dp[i][a[i].first*j]=1;
			}
			dp[i][0]=1;
			continue;
		}else{
			for (int k=0;k<=m;++k){
				dp[i][k]=dp[i-1][k];//不选 
			}
		}
		for (int j=1;j<=a[i].second && a[i].first*j<=m;++j){
			for (int k=a[i].first*j;k<=m;++k){
				dp[i][k]=(dp[i][k]+dp[i-1][k-a[i].first*j])%MOD;
			}
		}
		dp[i][0]=1;
	}
	for (int v=1;v<=m;++v){
		printf("%d ",dp[n-1][v]);
	}
	return 0;
}

这一课学的是通过前缀和差分优化各种东西。