链接：https://codeforces.com/problemset/problem/383/D
思路：dp[i][j]表示前i个数，和为j的方案数，可以由前面的方案转移过来，也可以从这里开始产生新的方案，然后统计贡献和即可。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
using namespace std;
typedef long long ll;
ll dp[2][22100];
int n;
const ll mod = 1e9 + 7;
void (ll &x, ll y){
x += y;
if(x >= mod) x -= mod;
}
int main(){
cin >> n;
int o = 0;
ll res = 0;
for(int i = 1; i <= n; i++){
int x;
cin >> x;
for(int j = 1000; j <= 21000; j++){
dp[o][j] = (dp[!o][j - x] + dp[!o][j + x]) % mod;
}
dp[o][11000 + x]++;
dp[o][11000 - x]++;
add(res, dp[o][11000]);
o = !o;
}
cout << res << 'n';
return 0;
}
|
近期评论