奇思妙想波奇酱
观察发现 b 很小,所以直接搜,但是还发现有点重复,记 f[x] 为 以 x 为端点后半段能否构造,显然可以记忆化,直接秒了。
#include<bits/stdc++.h>
// #define int long long
using namespace std;
using i64 = long long;
void solve() {
int n; cin >> n;
vector<int> b(n + 1);
vector<int> f(n + 1, -1);
for(int i = 1; i <= n; ++i) cin >> b[i];
function<bool(int, i64, int, bool)> dfs = [&](int x, i64 sum, int i, bool fl) -> bool {
// cout << x << " " << sum << " " << i << " " << fl << endl;
// if(x > n) return 0;
if(sum < 0 || sum > 1e8) return 0;
if(x == n) {
return fl ? sum == b[x] : sum == 0;
}
bool res = 0;
if(fl) {
res = dfs(x + 1, sum + i * i * b[x], i + 1, 1);
if(sum == b[x]) {
if(~f[x + 1]) res = f[x + 1];
else res |= f[x + 1] = dfs(x + 1, 0, 1, 1) || dfs(x + 1, b[x + 1], 1, 0);
}
}
else {
if(sum == 0) {
if(~f[x + 1]) res = f[x + 1];
else res = f[x + 1] = dfs(x + 1, 0, 1, 1) || dfs(x + 1, b[x + 1], 1, 0);
}
else res = dfs(x + 1, sum - i * i * b[x + 1], i + 1, 0);
}
return res;
};
cout << (dfs(0, 0, 0, 0) ? "Yes" : "No") << endl;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
while(t--) solve();
return 0;
}