#6397. 「THUPC2018」蛋糕 / Cake

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

最近,菲菲学会了做蛋糕,她做了一个 4D 的蛋糕送给牛牛,这个蛋糕的大小是: a \times b \times c \times d

蛋糕所有的表面都抹着奶油,牛牛想把蛋糕沿着与表面平行的超平面,切成 1 \times 1 \times 1 \times 1 的小块。

现在,牛牛想知道,在这些小块蛋糕中,有 0 个、 1 个、 2 个…… 8 个表面抹着奶油的有分别有多少块。

输入格式

输入包含多组数据,第一行一个整数 T 表示数据组数。( T <= 10000

接下来依次描述每组数据,对于每组数据:

  • 一行 4 个正整数 a b c d 。(四个正整数都在 10^6 以内)

输出格式

对于每组数据,输出 1 行:

  • 一行输出 9 个整数,分别表示有 0 个、 1 个、 2 个…… 8 个表面抹着奶油的小块蛋糕数量,所有值之间用单个空格隔开。为了防止答案过大,你只需要输出答案除以 2148473648 的余数。

样例

样例 1 输入

5
2 2 2 3
7 7 8 8
9 9 9 9
3 3 5 6
9 7 5 2

样例 1 输出

0 0 0 8 16 0 0 0 0
900 1320 724 176 16 0 0 0 0
2401 2744 1176 224 16 0 0 0 0
12 62 108 72 16 0 0 0 0
0 210 284 120 16 0 0 0 0

样例 1 解释

对于第一组数据,把 2 \times 2 \times 2 \times 3 的蛋糕切成小块后,共形成了 24 个小立方体,其中有 16 个小块分别与其他 4 个小块相邻,因此它们有 4 个面涂有奶油,而另外 8 个小块分别与其他 5 个小块相邻,因此它们有 3 个面涂有奶油。

数据范围与提示

来自 2018 清华大学学生程序设计竞赛暨高校邀请赛(THUPC2018),感谢 Pony.ai 对此次比赛的支持。

题解等资源可在 https://github.com/wangyurzee7/THUPC2018 查看。