g556: 白色世界(困難版)
Tags : DP
Accepted rate : 10人/12人 ( 83% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-11-15 23:32

Content

原題序請見g555。

只不過這次臨末來到的白色世界異常的大,所以道路也特別長,聰明的你可以幫幫他再算一次方法數嗎?

 

 

原題序:

在白色世界裡,所有東西都是白色的。有一天,臨末覺得白色世界實在太無聊了,於是帶著一些黑色的顏料進到白色世界,嘗試將這個世界染色。在與白色世界的村長討論過後,決定只在一條道路上實驗。為了讓村民適應,臨末將這條路分成好幾格,選任意的、任意個格子染色,但不能將連續的格子一起染色,否則村民會不適應。

問題來了:臨末共有幾種方式能夠達成此目的呢?(不能都不染色,否則達不到臨末的目的)

Input

第一行有1個整數t(1<=t<=300000),表示共有t筆測試資料

接下來有t行,每行一個整數n(1<=n<=10^18),表示道路的長度(格子數量)

Output

針對每個n,輸出共有幾種方法可以達成題目需求(每次輸出後換行)

由於答案可能很大,請mod 998244353後輸出

Sample Input #1
1
2
Sample Output #1
2
Sample Input #2
2
3
10
Sample Output #2
4
143
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (1%): 10.0s , <10M
公開 測資點#1 (49%): 10.0s , <10M
公開 測資點#2 (50%): 10.0s , <10M
Hint :

#0測資點保證所有數字皆<=300000

如果python或java的使用者發現複雜度正確但#1、#2測資點TLE,可以私訊我,會處理。(本人只會C++,沒有要卡python或java)

Tags:
DP
出處:
[管理者:
linlincaleb@... (臨末之頌)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」