CF1227F2 Wrong Answer on test 233 (Hard Version)

Your program fails again. This time it gets "Wrong answer on test 233" .This is the harder version of the problem. In this version, $ 1 \le n \le 2\cdot10^5 $ . You can hack this problem if you locked it. But you can hack the previous problem only if you locked both problems. The problem is to finish $ n $ one-choice-questions. Each of the questions contains $ k $ options, and only one of them is correct. The answer to the $ i $ -th question is $ h_{i} $ , and if your answer of the question $ i $ is $ h_{i} $ , you earn $ 1 $ point, otherwise, you earn $ 0 $ points for this question. The values $ h_1, h_2, \dots, h_n $ are known to you in this problem. However, you have a mistake in your program. It moves the answer clockwise! Consider all the $ n $ answers are written in a circle. Due to the mistake in your program, they are shifted by one cyclically. Formally, the mistake moves the answer for the question $ i $ to the question $ i \bmod n + 1 $ . So it moves the answer for the question $ 1 $ to question $ 2 $ , the answer for the question $ 2 $ to the question $ 3 $ , ..., the answer for the question $ n $ to the question $ 1 $ . We call all the $ n $ answers together an answer suit. There are $ k^n $ possible answer suits in total. You're wondering, how many answer suits satisfy the following condition: after moving clockwise by $ 1 $ , the total number of points of the new answer suit is strictly larger than the number of points of the old one. You need to find the answer modulo $ 998\,244\,353 $ . For example, if $ n = 5 $ , and your answer suit is $ a=[1,2,3,4,5] $ , it will submitted as $ a'=[5,1,2,3,4] $ because of a mistake. If the correct answer suit is $ h=[5,2,2,3,4] $ , the answer suit $ a $ earns $ 1 $ point and the answer suite $ a' $ earns $ 4 $ points. Since $ 4 > 1 $ , the answer suit $ a=[1,2,3,4,5] $ should be counted.

N/A

N/A

For the first example, valid answer suits are $ [2,1,1], [2,1,2], [2,1,3], [3,1,1], [3,1,2], [3,1,3], [3,2,1], [3,2,2], [3,2,3] $ .