a598: A. 果然我的高一平凡生活搞錯了。
標籤 : DP Dynamic Programming Math
通過比率 : 14人/14人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-05-27 21:00

內容

現在已經來到 $2021$ 年 $5$ 月的最後幾天,身為準教學的 tree 發現他的高一生活也即將步入尾聲。想想今年發生過的事......雖然不像某國家的高中生一樣,一下轉生異世界,一下會被莫名其妙地殺死,還會莫名其妙地復活,但是......首先發現自己被發去有國家棟樑的班、整年都被 $COVID-19$ 搞、每天戴口罩、當了 $108 課綱$ 第二屆白老鼠、發現自己是復旦末屆直升班、上了始業輔導、被 $9^{th}$ 教學 + 助教 + 顧問電爛、去了十分瀑布、寫了 $Discord$ $Bot$、發下二類三類選組單、二類三類取消變成要成立醫科班、醫科班不知為何只有 28 人填因此不成班、$COVID-19$ 在台灣爆發連續一個星期每日破百例、史無前例的遠距教學,每天在電腦前 $6$ ~ $8$ 小時......

奇怪,聽說高一生活不是應該風平浪靜嗎?!

為了適應這超展開劇情的高中生活,tree 必須做很多決定,讓自己可以繼續生活。

在每次做決定時都只有 $2$ 個選項,一個是比較保守的選項,另一個是比較激進的選項,每次選擇時都會造成生活有所改變,使他的生活有多種未來,但如果在 $n$ 次抉擇中,兩種不同的選法選擇激進選項的次數一樣多時就會使得這兩種選法邁向同種未來。

舉例:假設 $n = 3$ 且一種選法是 $激進、保守、激進$,另一種是 $保守、激進、激進$,則兩種選法都會邁向「選兩次激進選項」的未來。

請問在經過 $n$ 次抉擇後,依照 tree 所選的激進選項次數大小,每種未來會有幾種可能的選法?

 

輸入說明

每個測資點多筆測資。

第一行有一數 $T$,代表有幾個測資。

第二行 ~ 第 $T + 1$ 行,每行有一數 $n$,代表 tree 要做幾次選擇。

輸出說明

對於每個 $n$,根據每一種未來選擇激進選項 $i$ 次,輸出選法數 $a_0$ ~ $a_n$。

每個選法數間要空一格,輸出 $a_0$ ~ $a_n$ 後要換行。

範例輸入
2
1
3
範例輸出
1 1
1 3 3 1
測資資訊:
記憶體限制: 32 MB
公開 測資點#0 (20%): 0.6s , <1K
公開 測資點#1 (20%): 0.6s , <1K
公開 測資點#2 (19%): 0.6s , <1K
公開 測資點#3 (21%): 0.6s , <1M
公開 測資點#4 (20%): 0.6s , <1M
提示 :

要抓住正確的未來才活得下去

$\forall T \leq 10^5$

$1\leq n \leq 62$

請加 IO 優化

標籤:
DP Dynamic Programming Math
出處:
DDJ Regular Contest Round#2 [管理者:
fdhs109_tree (tree54145)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」