AcWing 278. 数字组合

思路

空集也是一种方案数, 一直加到m,中间不断记录次数就可以了 

代码

#include <bits/stdc++.h>
#define int long long#define F(i, a, b) for (int i = (a); i <= (b); i++)
#define dF(i, a, b) for (int i = (a); i >= (b); i--)using namespace std;typedef long long ll;
typedef pair<int, int> pii;const int N = 500005, M = (N << 1), inf = 1e16, mod = 1e9 + 7;int n, m, k, x, y, z, ans, t;
int w[N], f[N];void solve()
{cin >> n >> m;f[0] = 1;F (i, 1, n){int v;cin >> v;dF (j, m, v){f[j] += f[j - v];}}cout << f[m] << "\n";
}signed main()
{ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;
//	cin >> T;while (T -- ){solve();}
}