Emiya家今天的饭

【题目描述】

Emiya 是个擅长做菜的高中生，他共掌握 n 种烹饪方法，且会使用 m 种主要食材做菜。为了方便叙述，我们对烹饪方法从 1~n 编号，对主要食材从 1 ~m 编号。

Emiya 做的每道菜都将使用恰好一种烹饪方法与恰好一种主要食材。更具体地，Emiya 会做 ai,j 道不同的使用烹饪方法 i 和主要食材 j 的菜（1 ≤i≤n,1≤j≤m），这也意味着 Emiya 总共会做

道不同的菜。

Emiya 今天要准备一桌饭招待 Yazid 和 Rin 这对好朋友，然而三个人对菜的搭配有不同的要求，更具体地，对于一种包含 k 道菜的搭配方案而言：

（1）Emiya 不会让大家饿肚子，所以将做至少一道菜，即 k≥1

（2）Rin 希望品尝不同烹饪方法做出的菜，因此她要求每道菜的烹饪方法互不相同

（3）Yazid 不希望品尝太多同一食材做出的菜，因此他要求每种主要食材至多在一半的菜（即道菜）中被使用

这里的⌊x⌋ 为下取整函数，表示不超过 x 的最大整数。

这些要求难不倒 Emiya，但他想知道共有多少种不同的符合要求的搭配方案。两种方案不同，当且仅当存在至少一道菜在一种方案中出现，而不在另一种方案中出现。

Emiya 找到了你，请你帮他计算，你只需要告诉他符合所有要求的搭配方案数对质数998,244,353 取模的结果。

【输入格式】

从文件meal.in中读入数据。

第 1 行两个用单个空格隔开的整数 n,m。

第 2 行至第 n+1 行，每行 m 个用单个空格隔开的整数，其中第 i + 1行的 m 个数依次为 ai,1,ai,2,⋯,ai,m。

【输出格式】

输出到文件meal.out中。

仅一行一个整数，表示所求方案数对 998,244,353 取模的结果。

【样例 1 输入】

2 3 

1 0 1

0 1 1

【样例 1 输出】

3

【样例1解释】

由于在这个样例中，对于每组i，j，Emiya都最多只会做一道菜，因此我们直接通 过给出烹饪方法、主要食材的编号来描述一道菜。

符合要求的方案包括：

•做一道用烹饪方法1、主要食材1的菜和一道用烹饪方法2、主要食材2的菜

•做一道用烹饪方法1、主要食材1的菜和一道用烹饪方法2、主要食材3的菜

•做一道用烹饪方法1、主要食材3的菜和一道用烹饪方法2、主要食材2的菜

 因此输出结果为3 mod 998,244,353 = 3。

需要注意的是，所有只包含一道菜的方案都是不符合要求的，因为唯一的主要食材 在超过一半的菜中出现，这不满足Yazid的要求。

【样例2输入】

3 3

1 2 3

4 5 0

6 0 0

【样例2输出】

190

【样例2解释】

Emiya必须至少做2道菜。

做2道菜的符合要求的方案数为100。

做3道菜的符合要求的方案数为90。

因此符合要求的方案数为100 + 90 = 190。

【样例3输入】

5 5

1 0 0 1 1

0 1 0 1 0

1 1 1 1 0

1 0 1 0 1

0 1 1 0 1

【样例3输出】

742

【数据范围】

对于所有测试点，保证 1 ≤n≤ 100, 1 ≤ m ≤ 2000, 0≤ai，j< 998,244,353。

划分

【题目描述】

2048年，第三十届CSP认证的考场上，作为选手的小明打开了第一题。这个题的 样例有n组数据，数据从1~n编号，i号数据的规模为ai。

小明对该题设计出了一个暴力程序，对于一组规模为u的数据，该程序的运行时 间为u^2。然而这个程序运行完一组规模为u的数据之后，它将在任何一组规模小于u 的数据上运行错误。样例中的ai,不一定递增，但小明又想在不修改程序的情况下正确 运行样例，于是小明决定使用一种非常原始的解决方案：将所有数据划分成若干个数据 段，段内数据编号连续，接着将同一段内的数据合并成新数据，其规模等于段内原数据 的规模之和.小明将让新数据的规模能够递增。

也就是说，小明需要找到一些分界点使得

注意P可以为0且此时k0 = 0,也就是小明可以将所有数据合并在一起运行。

小明希望他的程序在正确运行样例情况下，运行时间也能尽量小，也就是最小化

小明觉得这个问题非常有趣，并向你请教：给定n和ai,请你求出最优划分方案 下，小明的程序的最小运行时间。

【输入格式】

从文件partition.in中读入数据。

由于本题的数据范围较大，部分测试点的ai将在程序内生成。

第一行两个整数n.type. n的意义见题目描述，type表示输入方式。

1.若type = 0.则该测试点的ai直接给出。输入文件接下来：第二行n个以空格 分隔的整数ai，表示每组数据的规模。

2.若type = 1则该测试点的ai将特殊生成，生成方式见后文。输入文件接下来: 第二行六个以空格分隔的整数x,y,z,b1,b2,m。 接下来m行中，第i行包含三个以空格分隔的正整数pi,li,ri。

对于type = 1的23 ~ 25号测试点，ai的生成方式如下：

给定整数x,y,z,b1，b2，m,以及m个三元组（pi，li，ri）。

保证 n2。 若 n > 2,则

保证

对于所有则有ai=（bi   mod（rj-lj+1））+lj

上述数据生成方式仅是为了减少输入量大小，标准算法不依赖于该生成方式。

【输出格式】

输出到文件partition.out中。

输出一行一个整数，表示答案。

【样例1输入】

5 0

5 17 9 9

【样例1输出】

247

【样例1解释】

最优的划分方案为{5,1},{7},{9},{9}。由5 + 1<=7<=9<=9知该方案合法。

答案为(5 + 1)^2 + 7^2 + 9^2 + 9^2 = 247。

虽然划分方案{5}，{1},{7},{9},{9}对应的运行时间比247小，但它不是一组合法 方案，因为5>1。

虽然划分方案{5},{1,7},{9},{9}合法，但该方案对应的运行时间为251,比247大。

【样例2输入】

10 0

5677462 13 19 9

【样例2输出】

1256

【样例2解释】

最优的划分方案为{5},{6}，{7}，{7},{4,6，2},{13},{19,9}。

【数据范围】

所有测试点满足：type € {0,1} , 2 < =n <= 4 x 10^7 , 1 < =ai,<= 10^9 , 1 <=m < =10^5 , 1 < =li <= ri <= 10^9 , 0 < x,y,z,b1,b2 < 2^30。

树的重心

小简单正在学习离散数学，今天的内容是图论基础，在课上他做了如下两条笔记：

1.一个大小为n的树由n个结点与n-1条无向边构成，且满足任意两个结点间有 且仅有一条简单路径。在树中删去一个结点及与它关联的边，树将分裂为若干个 子树；而在树中删去一条边（保留关联结点，下同），树将分裂为恰好两个子树。

2.对于一个大小为n的树与任意一个树中结点c,称c是该树的重心当且仅当在树 中删去c及与它关联的边后，分裂出的所有子树的大小均不超过（其中Lx」 是下取整函数）。对于包含至少一个结点的树.它的重心只可能有1或2个。

课后老师给出了一个大小为n的树S,树中结点从1~n编号。小简单的课后作业 是求出S单独删去每条边后，分裂出的两个子树的重心编号和之和。即：

上式中，E表示树S的边集，（u，n）表示一条连接u号点和V号点的边。S'u与S'v 分别表示树S删去边（u，v）后，u号点与V号点所在的被分裂出的子树。

小简单觉得作业并不简单，只好向你求助，请你教教他。

【输入格式】

从文件centroid.in中读入数据。

本题输入包含多组测试数据。

第一行一个整数T表示数据组数。

接下来依次给岀每组输入数据，对于每组数据：

第一行一个整数n表示树S的大小。

接下来n -1行，每行两个以空格分隔的整数 ui，vi，表示树中的一条边（ui，vi）。

【输出格式】

输出到文件centroid.out中。

共T行，每行一个整数.第i行的整数表示：第i组数据给岀的树单独删去每条边 后，分裂出的两个子树的重心编号和之和。

【样例1输入】

2

5

12

23

24

35

7

1 2

1 3

1 4

3 5

3 6

6 7

【样例1输出】

32

56

【样例1解释】

对于第一组数据:

删去边（1,2）, 1号点所在子树重心编号为｛1｝, 2号点所在子树重心编号为｛2,3｝。 删去边（2,3）, 2号点所在子树重心编号为⑵，3号点所在子树重心编号为｛3,5｝。

删去边（2,4）, 2号点所在子树重心编号为｛2,3｝, 4号点所在子树重心编号为｛4｝。 删去边（3,5）, 3号点所在子树重心编号为｛2｝, 5号点所在子树重心编号为｛5｝。

因此答案为 1 + 2 + 3 + 2 + 3 + 5 + 2 + 3 + 4 + 2 + 5 = 32。

【数据范围】

表中特殊性质一栏，两个变量的含义为存在一个1~n的排列使得: 

A：树的形态是一条链。即存在一条边(pi,pi+1)。

B：树的形态是一个完美二叉树。即存在两条边(Pi，P2i)与(Pi，P2i+1)。 对于所有测试点：保证给岀的图是一个树。