(mathcal{Description})
Link.
给定 ({a_n})，把每个元素划分入可重集 (R,G,B) 中的恰好一个，求满足 (sum R,sum G,sum B) 能够作为正面积三角形三边的划分方案数。对 (998244353) 取模。
(n,a_ile300)。
(mathcal{Solution})
不妨令 (sum R,sum Glesum B)（注意 (sum R) 和 (sum G) 不钦定偏序关系），正难则反，考虑用总方案数 (3^n) 减去 (3) 倍 (sum R+sum Gle sum B) 的方案数。令 (f(i,j)) 表示考虑了前 (i) 个数，(sum R+sum G=j) 的方案数。转移显然：
[f(i,j)=f(i-1,j)+2f(i-1,j-a_i)
]
不过，这样求出来的方案数中包含了 (R=varnothing) 或 (Q=varnothing) 的方案数，因而 (sum R+sum G=sum B) 的情形会算重。把转移方程的系数 (2) 去掉再来一遍补上多算的答案即可。
(mathcal{Code})
/* Clearink */
#include <cstdio>
const int MAXN = 300, MOD = 998244353;
int n, S, a[MAXN + 5], f[MAXN * MAXN + 5];
inline int mul ( const long long a, const int b ) { return a * b % MOD; }
inline int sub ( int a, const int b ) { return ( a -= b ) < 0 ? a + MOD : a; }
inline int add ( int a, const int b ) { return ( a += b ) < MOD ? a : a - MOD; }
inline int qkpow ( int a, int b ) {
int ret = 1;
for ( ; b; a = mul ( a, a ), b >>= 1 ) ret = mul ( ret, b & 1 ? a : 1 );
return ret;
}
int main () {
scanf ( "%d", &n );
for ( int i = 1; i <= n; ++ i ) scanf ( "%d", &a[i] ), S += a[i];
f[0] = 1;
for ( int i = 1; i <= n; ++ i ) {
for ( int j = S >> 1; j >= a[i]; -- j ) {
f[j] = add ( f[j], mul ( 2, f[j - a[i]] ) );
}
}
int ans = qkpow ( 3, n );
for ( int i = 0; i <= S >> 1; ++ i ) ans = sub ( ans, mul ( 3, f[i] ) );
if ( S & 1 ) return printf ( "%d
", ans ), 0;
for ( int i = 0; i <= S >> 1; ++ i ) f[i] = 0;
f[0] = 1;
for ( int i = 1; i <= n; ++ i ) {
for ( int j = S >> 1; j >= a[i]; -- j ) {
f[j] = add ( f[j], f[j - a[i]] );
}
}
ans = add ( ans, mul ( 3, f[S >> 1] ) );
printf ( "%d
", ans );
return 0;
}
(mathcal{Details})
正难则反吖！