爱做实验的平平经常使用天平称量重物，有一天他发现，在天平右边托盘中放置了 w 克的重物时，在左边托盘中用好几种不同的砝码放置方案都可以让天平进入平衡状态。他很想知道，用手头 n 个不同重量的砝码，究竟有多少种不同的放置方案能与这个 w 克的重物平衡。 你能否编一个代码帮他解决这个问题?由于答案可能很大，所以只需输出方案总数除以 201809 的余数。使用c++解决

这是一个经典的背包问题，可以使用动态规划来解决。设 $dp[i][j]$ 表示用前 $i$ 个砝码能否组成重量为 $j$ 的方案数，则有状态转移方程：

$$dp[i][j] = (dp[i-1][j-w_i] + dp[i-1][j])\%201809$$

其中 $w_i$ 表示第 $i$ 个砝码的重量。

最终的答案为 $dp[n][w]$，其中 $n$ 表示砝码的个数。

下面是 C++ 代码实现：

#include <iostream>
#include <cstring>
using namespace std;

const int maxn = 1005;
const int mod = 201809;

int dp[maxn][maxn];

int main() {
    int n, w;
    cin >> n >> w;
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        int wi;
        cin >> wi;
        for (int j = 0; j <= w; j++) {
            dp[i][j] = dp[i-1][j];
            if (j >= wi) {
                dp[i][j] = (dp[i][j] + dp[i-1][j-wi]) % mod;
            }
        }
    }
    cout << dp[n][w] << endl;
    return 0;
}