题意：

有\(n\)个石头，每个石头有权值，可以给它们染'R', 'G', 'B'三种颜色，如下定义一种染色方案为合法方案：

• 所有石头都染上了一种颜色
• 令\(R, G, B\)为染了'R', 染了'G', 染了'B'的所有石头的权值和，存在一个三角形的三边为\(R, G, B\)

求合法方案数模\(998244353\)

思路：

考虑总方案数为\(3^n\)，我们考虑怎么求出不合法的方案数。令\(dp[i][j]\)表示到第\(i\)个石头，两条短边和为\(j\)的方案数

但是我们注意到，如果\(sum\)是偶数的话，那么：

1. \(R = B = \frac{sum}{2}\)和\(B = R = \frac{sum}{2}\)
2. \(R = G = \frac{sum}{2}\)和\(G = R = \frac{sum}{2}\)
3. \(B = G = \frac{sum}{2}\)和\(G = B = \frac{sum}{2}\)

贡献会重复算一遍，再\(dp\)一次，删掉一份贡献即可。

代码：

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define N 310

const ll p = 998244353;

int n, a[N];

ll f[N * N], g[N * N], all;

int main() {

	while (scanf("%d", &n) != EOF) {

		ll sum = 0, mid;

		all = 1;

		for (int i = 1; i <= n; ++i) {

			scanf("%d", a + i);

			sum += a[i];

			all = (all * 3) % p;

		}

		mid = sum / 2;

		memset(f, 0, sizeof f);

		f[0] = 1;

		for (int i = 1; i <= n; ++i) {

			for (int j = sum - a[i]; j >= 0; --j) {

				f[j + a[i]] = (f[j + a[i]] + f[j] * 2 % p) % p;

			}

		}

		ll res = 0;

		for (int i = 0; i <= mid; ++i) {

			res = (res + f[i]) % p;

		}

		if (sum % 2 == 0) {

			memset(g, 0, sizeof g);

			g[0] = 1;

			for (int i = 1; i <= n; ++i) {

				for (int j = sum - a[i]; j >= 0; --j) {

					g[j + a[i]] = (g[j + a[i]] + g[j]) % p;

				}

			}

			res = (res - g[mid] + p) % p;

		}

		printf("%lld\n", (all - (res * 3) % p + p) % p);

	}

	return 0;

}