题意： 有\(n\)个石头，每个石头有权值，可以给它们染'R', 'G', 'B'三种颜色，如下定义一种染色方案为合法方案：
所有石头都染上了一种颜色令\(R, G, B\)为染了'R', 染了'G', 染了'B'的所有石头的权值和，存在一个三角形的三边为\(R, G, B\)求合法方案数模\(998244353\)
思路： 考虑总方案数为\(3^n\)，我们考虑怎么求出不合法的方案数。令\(dp[i][j]\)表示到第\(i\)个石头，两条短边和为\(j\)的方案数 但是我们注意到，如果\(sum\)是偶数的话，那么：
\(R = B = \frac{sum}{2}\)和\(B = R = \frac{sum}{2}\)\(R = G = \frac{sum}{2}\)和\(G = R = \frac{sum}{2}\)\(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; }转载于:https://www.cnblogs.com/Dup4/p/10750105.html
相关资源：JAVA上百实例源码以及开源项目