k914. 肯肯肯的正方形 - 高中生程式解題系統

內容

有 $N$ 個正方形，它們的左上及右下角之間有線段連接，把所有正方形連接起來形成下方的圖形 :

現在我們定義 一筆畫 為 : 一個路徑滿足恰走過所有的邊各一次。

現在想問你如果從左上角的位置出發 (也就是紅點的位置) 一筆畫到右下角的位置 (藍點的位置)，有幾種方法數 ? 因為答案可能很大，請模 $998244353$ 。詳情可參考範例及提示。

輸入說明

輸入有個正整數 $N (1 \leq N \leq 10^{18})$ ，代表正方形的數目。

輸出說明

輸出一筆畫的方法數模 $998244353$ 。

範例輸入 #1

範例輸出 #1

範例輸入 #2

範例輸出 #2

範例輸入 #3

範例輸出 #3

345406998

測資資訊：

記憶體限制： 512 MB
不公開測資點#0 (5%): 1.0s , <1K
不公開測資點#1 (5%): 1.0s , <1K
不公開測資點#2 (5%): 1.0s , <1K
不公開測資點#3 (5%): 1.0s , <1K
不公開測資點#4 (5%): 1.0s , <1K
不公開測資點#5 (5%): 1.0s , <1K
不公開測資點#6 (5%): 1.0s , <1K
不公開測資點#7 (5%): 1.0s , <1K
不公開測資點#8 (5%): 1.0s , <1K
不公開測資點#9 (5%): 1.0s , <1K
不公開測資點#10 (5%): 1.0s , <1K
不公開測資點#11 (5%): 1.0s , <1K
不公開測資點#12 (5%): 1.0s , <1K
不公開測資點#13 (5%): 1.0s , <1K
不公開測資點#14 (5%): 1.0s , <1K
不公開測資點#15 (5%): 1.0s , <1K
不公開測資點#16 (5%): 1.0s , <1K
不公開測資點#17 (5%): 1.0s , <1K
不公開測資點#18 (5%): 1.0s , <1K
不公開測資點#19 (5%): 1.0s , <1K

提示：

範例輸入 # 1:

上方是 $N = 1$ 的圖形，總共有 $6$ 種走法 :

$A \to B \to C \to A \to D \to C$

$A \to B \to C \to D \to A \to C$

$A \to C \to B \to A \to D \to C$

$A \to C \to D \to A \to B \to C$

$A \to D \to C \to A \to B \to C$

$A \to D \to C \to B \to A \to C$

範例輸入 # 2 :

以下為 $N = 2$ 的圖形，可計算出有 $44$ 種走法。

範例輸入 # 3 :

請記得將答案模 $998244353$ 。

配分 :

$25 % : N \leq 5$

$25 % : N \leq 100$

$50 % :$ 無其他限制

註：題目不是我出的，我只是幫忙放上來，若有任何問題，請洽提出這題的人與準備這題的人

標籤:

dp math

出處:

肯肯肯的數學課本 [管理者： beckzerojudge@gmail.com

becaido (Caido) ]

編號	身分	題目	主題	人氣	發表日期
35879	r1cky (hehe)	k914	__題解	464	2023-06-21 13:47