Different Arrays

Created by LXC on Thu Oct 19 01:56:40 2023

https://codeforces.com/problemset/problem/1783/D

ranting: 2000

tag: brute force, dp, implementation

problem

给出一个数组$a_1, a_2, \cdots, a_n$

对于i从2到n-1，我们让$a_i$执行二选一操作，要么让$a_{i-1} += a_i, a_{i+1} -= a_i$，要么让$a_{i-1} -= a_i, a_{i+1} += a_i$

问总共会产生多少种不同的数组。

$3 \le n \le 300$，$0 \le a_i \le 300$

solution

注意到当我们对$a_i$操作后，$a_{i+2}, \cdots, a_n$是没有发生变化的。所以我们可以考虑前缀作为子问题。

对于$a_i$的操作会导致$a_{i-1}$和$a_{i+1}$发生变化，但是$a_{i-1}$的变化是不重要的，因为后续是对$a_{i+1}$进行操作。所以我们需要考虑每个$a_{i}$可能的值。

注意到$0 \le a_{i} \le 300$，当我们操作$a_i$时，$a_i$当前的值可能时前面的数加加减减得到的。大概在$[-90000, 90000]$。

我们定义$f_{i,j}$为操作$a_{i-1}$时，让$a_{i} = j$的种数。

那么对于$f_{i,j}$存在，就有$f_{i+1, a_{i+1} \pm j} += f_{i,j}$

初始时$f_{2, a_2} = 1$

答案为$\sum \limits_{i=-90000}^{90000}f_{n, i}$

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 100005
#define MOD 998244353
using namespace std;

int f[301][2*N];

void sol() {
	int n;
    cin >> n;
    vector<int> a(n);
    for (auto& i:a) cin >> i;
    f[1][a[1]+N] = 1;
    for (int i=1; i+1<n; i++) {
        for (int j=-90000; j<=90000; j++) {
            if(f[i][j+N]) {
                f[i+1][a[i+1]-j+N] += f[i][j+N];
                f[i+1][a[i+1]-j+N] %= MOD;
                if (j!=0) {
                    f[i+1][a[i+1]+j+N] += f[i][j+N];
                    f[i+1][a[i+1]+j+N] %= MOD;
                }
            }
        }
    }
    ll ans = 0;
    for (int i=-90000; i<=90000; i++) {
        ans += f[n-1][i+N];
        ans %= MOD;
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}