number of subsets of an array of n elements having sum equal to k for each k from 1 to m
| 234 | }; |
| 235 | // number of subsets of an array of n elements having sum equal to k for each k from 1 to m |
| 236 | int32_t main() { |
| 237 | ios_base::sync_with_stdio(0); |
| 238 | cin.tie(0); |
| 239 | int n, m; cin >> n >> m; |
| 240 | vector<int> a(m + 1, 0); |
| 241 | for (int i = 0; i < n; i++) { |
| 242 | int k; cin >> k; // k >= 1, handle [k = 0] separately |
| 243 | if (k <= m) a[k]++; |
| 244 | } |
| 245 | poly p(m + 1, 0); |
| 246 | for (int i = 1; i <= m; i++) { |
| 247 | for (int j = 1; i * j <= m; j++) { |
| 248 | if (j & 1) p.a[i * j] += mint(a[i]) / j; |
| 249 | else p.a[i * j] -= mint(a[i]) / j; |
| 250 | } |
| 251 | } |
| 252 | p = p.exp(m + 1); |
| 253 | for (int i = 1; i <= m; i++) cout << p[i] << ' '; cout << '\n'; // check for m = 0 |
| 254 | return 0; |
| 255 | } |
| 256 | // https://judge.yosupo.jp/problem/sharp_p_subset_sum |