题目详情题解（0）讨论（0）提交记录（0）

AT_tenka1_2019_d.Three Colors

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定 NN 个整数，第 ii 个整数为 aia_i。请将所有给定的整数分别涂成红色、绿色或蓝色中的一种，使得满足以下条件的方案数对 998244353998244353 取模后输出。

  • 分别用 R,G,BR,G,B 表示被涂成红色、绿色、蓝色的整数之和。存在一个三角形，其三边长度分别为 R,G,BR,G,B，且面积为正数。

输入格式

输入以以下格式从标准输入读入。

NN a1a_1 a2a_2 …\ldots aNa_N

输出格式

输出所有整数的涂色方案数，使其满足条件，并对 998244353998244353 取模。

输入输出样例

  • 输入#1

    4
1
1
1
2

    输出#1

    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

说明/提示

限制条件

  • 3≤N≤3003 \leq N \leq 300
  • 1≤ai≤300 (1≤i≤N)1 \leq a_i \leq 300\ (1 \leq i \leq N)
  • 输入均为整数

样例解释 1

只有将三边的长度分别涂成 1,2,21,2,2 的方式才能组成三角形，这样的涂色方案共有 1818 种。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页