AtCoder Tenka1 Task D: Three Colors
英文题面
Problem Statement
You are given N integers. The i-th integer is ai. Find the number, modulo 998244353, of ways to paint each of the integers red, green or blue so that the following condition is satisfied:
Let R, G and B be the sums of the integers painted red, green and blue, respectively. There exists a triangle with positive area whose sides have lengths R, G and B.
Constraints
3≤N≤300
1≤ai≤300(1≤i≤N)
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
a1
:
aN
Output
Print the number, modulo 998244353, of ways to paint each of the integers red, green or blue so that the condition is satisfied.
Sample Input 1
4
1
1
1
2
Sample Output 1
18
We can only paint the integers so that the lengths of the sides of the triangle will be 1, 2 and 2, and there are 18 such ways.
Sample Input 2
6
1
3
2
3
5
2
Sample Output 2
150
Sample Input 3
20
3
1
4
1
5
9
2
6
5
3
5
8
9
7
9
3
2
3
8
4
Sample Output 3
563038556
中文题面(手动翻译)
题面描述
你有 N 个整数。第 i 个整数是 $ a_i $。求出将数字涂成红色,绿色和蓝色整数的方法总数,并以满足以下条件:
设 R,G 和 B 分别为涂成红色,绿色和蓝色的整数之和。存一个正面积的三角形的三边长分别为 R,G,B。
数据范围
3≤N≤300
$ 1≤a_i≤300(1≤a_i≤N) $
输入中的所有值都是整数。
输入
输入由标准输入以下列格式给出:
N
$ a_1 $
$ a_2 $
.
.
.
$ a_n $
输出
打印数字,模 998244353,绘制红色,绿色或蓝色的每个整数的方法,以满足条件。
样例输入 1
4
1
1
1
2
样例输出 1
18
我们可以只画整数,使三角形的边的长度将是 1,2 和 2,并有 18 种这样的方式。
样例输入 2
6
1
3
2
3
5
2
样例输出 2
150
样例输入 3
20
3
1
4
1
5
9
2
6
5
3
5
8
9
7
9
3
2
3
8
4
样例输出 3
563038556
解题思路
这是一道非常有趣的 dp 问题。一看数据范围就知道朴素是过不了的。
我们设 dpn 表示前 i 个数字,B 的总和为 j 的方案数。
详见代码。
代码
#include<iostream>
#include<cstdio>
#include <cstring>
using namespace std;
const int MaxN = 300;
const long long mod = 998244353;
a[i]这个数 只能加在R、G、B中
dp[i][j] = dp[i-1][j - a[i]] + dp[i-1][j] * 2LL;
*/
long long dp[MaxN + 5][MaxN * MaxN + 5];
int a[MaxN + 5];
int main(){
long long ans = 1, res = 0;//ans代表总方案数,res代表不可能的方案数
int n, sum = 0;//sum代表三条边的总和,最大的那条边 < sum/2
scanf("%d", &n);
for(int i = 1;i <= n;i++){
scanf("%d",&a[i]);
sum += a[i];
ans = ans * 3LL % mod;//3LL就是在long long类型下的3
}
for(int i = 1;i <= sum;i++) dp[0][i] = 0;//0个数不可能加起来不等于0,所以方案数为0
dp[0][0] = 1;
for(int i = 1;i <= n;i++){
for(int j = 0;j <= sum;j++){
dp[i][j] = dp[i - 1][j] * 2LL % mod;//这个数加在R或G的两种情况
if(j >= a[i]) dp[i][j] = (dp[i][j] + dp[i - 1][j - a[i]]) % mod;//如果可以,就把这个数加载B上
}
}
for(int i = (sum + 1) / 2;i <= sum;i++) res = (res + dp[n][i]) % mod;
// res = B总和大于等于 sum/2的方案数
//------------由于像n n 0这种情况要减去,并且只有偶数是会有这种情况。------------
if(sum % 2 == 0){
for(int i = 1;i <= n;i++){
for(int j = 0;j <= sum;j++){
dp[i][j] = dp[i - 1][j] % mod;//只加一个数,所以不用*2
if(j >= a[i]) dp[i][j] = (dp[i][j] + dp[i - 1][j - a[i]]) % mod;
}
}//上一次dp更新不会影响到这一次是因为dp[0]没有改变
res = (res - dp[n][sum/2LL] + mod % mod);//这句话即res减去B占一半,另一个颜色也占一半的可能性
//+mod%mod是为了防止前面是负数
}
//---------------------------------------------------------------------------
printf("%lld\n",(ans - res * 3LL % mod + mod) % mod);//*3LL是因为这里只有B一种情况,其他情况同理
return 0;
}
全Tenka1 Beginner 3000多人中只有四个人做出来了。。。
这是我打atcoder Beginner到现在看到过的AC题数最少的题目了。