#P13090. [FJCPC 2025] XCPC

[FJCPC 2025] XCPC

题目描述

XCPC 赛事拥有金、银、铜、铁四种奖牌。作为一名参与该赛事的魔法师,小 A 可通过金、银、铜、铁四种奖牌作为媒介,施展“红日初升”法阵,召唤太阳,祈求保佑。

在施展“红日初升”法阵的过程中,每一个奖牌都可以提供光亮值。其中金、银、铜、铁奖牌分别具有 44332211 的光亮值。而施展“红日初升”法阵要求所有奖牌的光亮值之和大于等于 pp

初始时小 A 有 nn 块铁牌,他可以通过炼金术进行奖牌转换:将 22 个铁牌合成 11 个铜牌、将 22 个铜牌合成 11 个银牌、将 22 个银牌合成 11 个金牌。

假设用四元组 (a1,a2,a3,a4)(a_1,a_2,a_3,a_4) 分别表示金、银、铜、铁奖牌的数量。请回答以下 nn 个问题,其中第 i (1in)i~(1\le i\le n) 个问题是:

  • 初始有 nn 块铁牌,最终有多少种不同的四元组 (a1,a2,a3,a4)(a_1,a_2,a_3,a_4),同时满足:

(1)一共有 ii 个牌子,即 a1+a2+a3+a4=ia_1+a_2+a_3+a_4=i

(2)可以施展“红日初升”法阵,即 4a1+3a2+2a3+a4p4a_1+3a_2+2a_3+a_4\ge p

其中 pp 通过输入给定。

两个四元组不同当且仅当它们存在某一位对应的数字不同。

输入格式

第一行输入两个整数 n,p (1pn106)n,p~(1\le p\le n\le 10^6),用空格相隔,分别表示初始有 nn 个奖牌,以及问题要求的奖牌价值之和大于等于 pp

输出格式

输出一行 nn 个整数,用空格相隔,第 i (1in)i~(1\le i\le n) 个数字表示第 ii 个问题的答案。

8 7

0 0 1 2 2 1 1 1

10 8

0 0 1 2 2 2 2 1 1 1
12 1

0 1 2 2 3 3 2 2 2 1 1 1

提示

样例解释:对于样例一,初始的 88 个铁牌最终可以得到多个四元组,以下列出光亮值之和大于等于 77 的:

  • 1,21,2 个问题:(无);

  • 33 个问题:(0,1,2,0)(0,1,2,0)

  • 44 个问题:(0,0,4,0),(0,1,1,2)(0,0,4,0),(0,1,1,2)

  • 55 个问题:(0,1,0,4),(0,0,3,2)(0,1,0,4),(0,0,3,2)

  • 66 个问题:(0,0,2,4)(0,0,2,4)

  • 77 个问题:(0,0,1,6)(0,0,1,6)

  • 88 个问题:(0,0,0,8)(0,0,0,8)