This is the harder version of the problem. In this version, 1≤𝑛≤2⋅105. 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 𝑛 one-choice-questions. Each of the questions contains 𝑘 options, and only one of them is correct. The answer to the 𝑖-th question is ℎ𝑖, and if your answer of the question 𝑖 is ℎ𝑖, you earn 1 point, otherwise, you earn 0 points for this question. The values ℎ1,ℎ2,…,ℎ𝑛 are known to you in this problem.

However, you have a mistake in your program. It moves the answer clockwise! Consider all the 𝑛 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 𝑖 to the question 𝑖mod𝑛+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 𝑛 to the question 1.

We call all the 𝑛 answers together an answer suit. There are 𝑘𝑛 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 998244353.

For example, if 𝑛=5, and your answer suit is 𝑎=[1,2,3,4,5], it will submitted as 𝑎′=[5,1,2,3,4] because of a mistake. If the correct answer suit is ℎ=[5,2,2,3,4], the answer suit 𝑎 earns 1 point and the answer suite 𝑎′ earns 4 points. Since 4>1, the answer suit 𝑎=[1,2,3,4,5] should be counted.

链接🔗

「CodeForces 1261D」Wrong Answer on test 233

题解

考虑每个位置所填答案对正确数量的影响。如果s[i]==s[i+1]s[i] == s[i+1],那么正确数量无论如何都不会发生变化,因为 如果所填答案 x==s[i]x== s[i] 那么 x==s[i+1]x == s[i+1] ,反之亦然。
如果s[i]!=s[i+1]s[i] != s[i+1] 那么就会出现3种情况
正确数量加1,x != s[i] && x == s[i+1]
正确数量减1,x == s[i] && x != s[i+1]
正确数量不变, other
所有位置填写答案的不同方案总数为knk^n,会有正确答案多于原先的,正确答案少于原先的,正确答案等于原先的三种情况,思考后可以发现,多于原先和少于原先的方案数是相等的,所以我们所求多于原先的方案数可以转化为求(总方案数 - 答案等于原先方案数)/2,
因为要求答案数等于原先方案数,所以当选取了ii个正确数量+1的方案数时,就必须选对应的ii个正确数量-1的方案数,所以我们可以考虑枚举ii,然后通过组合原理求出总数

代码

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxd = 2e5+10;
typedef long long ll;
const int mod = 998244353;
int n,k,num,a[maxd];
long long fac[maxd];
ll pow(ll a,ll b)
{
    ll ans = 1ll;
    while(b)
    {
        if(b&1) ans = ans * a %mod;
        a = a * a % mod;
        b /= 2;
    }
    return ans;
}
ll C(ll a,ll b)
{
    return 1ll* (fac[a] * pow(fac[b],1ll * mod-2) % mod) * pow(fac[a-b],mod-2) %mod;
}
int main()
{
//    freopen("a.in","r",stdin);
//    freopen("k.out","w",stdout);
    scanf("%d %d",&n,&k);
    if(k == 1) {printf("0");return 0;}
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<n;i++) if(a[i] != a[i+1]) num++; num += (a[1] != a[n]);
 
    fac[0] = 1ll;for(int i=1;i<maxd;i++) fac[i] = 1ll * fac[i-1] * i %mod;
 
//    for(int i=1;i<=n;i++)
//
    long long ans = 0ll;
 
    for(int i=0;i * 2 <= num;i++) {
        long long tmp = C(num, i) * C(num - i, i) % mod * pow(k - 2, num - i - i) % mod * pow(k, n-num) % mod;
        ans = (tmp + ans) % mod;
    }
    //for(int i=1;i<=10;i++) printf("%lld \n",pow(2,i));
    printf("%lld\n",((pow(k,n) - ans)%mod  + mod ) %mod * pow(2,mod-2) %mod );
    return 0;
}