h318. 隨便亂坐!
Tags :
Accepted rate : 5人/6人 ( 83% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-12-25 12:07

Content

ㄅㄧㄎㄞㄉㄡ 是一名國小老師;然後ㄅㄧㄎㄞㄉㄡ老師為了讓新班級小朋友們認識彼此,他就設計了一個遊戲。

他有 $\color{black}{N}$ 個班級,第 $\color{black}{i}$ 個班級有 $\color{black}{i+2}$ 位學生,他們的座號是 $\color{black}{i+2}$,且他們都知道自己的座號。

教室裡有 $\color{black}{i+2}$ 個椅子為成一圈,然後ㄅㄧㄎㄞㄉㄡ老師要求他們隨變找一個位子坐,因為他們彼此不認識,所以他們不知道別人的座號,然後全部人都入座之後,ㄅㄧㄎㄞㄉㄡ老師要大家詢問自己左邊的人的座號,如果他左邊那個的人的座號跟他相差大於等於 $2$ 的話,就要把左手舉起來。

他要計算 $\color{black}{N}$ 個班中把左手舉起來的人的個數的期望值的總和是多少。

Input

 每筆測資第一行有一個數字 $\color{black}{T(1\leq T\leq 10^6)}$,代表有 $\color{black}{T}$ 組測資,然後接下來 $\color{black}{T}$ 行,每行有一個正整數 $\color{black}{N(1\leq N\leq 10^{18})}$,代表他帶了幾個班級。

Output

對於每組策資,輸出 $1$ 行代表答案。

答案如果是分數,$\color{black}{ans=\frac{p}{q},\gcd(p,q)=1}$,

請輸出 $\color{black}{p\times q^{-1}}$,由於答案可能很大,輸出請模 $998244353$

Sample Input #1
4
1
2
48763
101648763
Sample Output #1
1
3
190695113
597327153
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (10%): 3.0s , <10M
公開 測資點#1 (20%): 3.0s , <10M
公開 測資點#2 (70%): 3.0s , <50M
Hint :

 

以這張圖為例子,座號1,2,3,5的人會把左手舉起來,所以把左手舉起來的人的個數就是4。

 

 

第一筆測資 $\color{black}{N\le 100}$
第二筆測資 $\color{black}{N\le 10^6}$
第三筆測資沒有限制  

 

2022 4/8更新範例測資

Tags:
出處:
[管理者: Easonsfriend(becaidorz) ]


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