闲话
机房歌单更新了（
我写了一首《第三心脏》上去
被 muel 和 gtm 说要指明 miku 唱的（
我倒是觉得饭自己唱的也蛮好听的就是了
今日推歌：无理无智
不为什么 只是最近老是哼哼哼
题解
shik 吞进去又吐出来。ber♂宇和抵德纠缠个不清。天空中的素数还没有降下。
你站在椭圆的一♂焦,伟大尼特向你发问。
T1 西克（Shik）
分两段考虑：\(u \to \text{lca} \to v\)。
\(u \to \text{lca}\) 是经典问题 可以作树上倍增 \(O(n \log n) - O(\log n)\) 得到。我们可以得到未超过 \(\text{lca}\) 的最高节点，这时这一侧不可能有贡献，我们带着 \(z\) 到第二段。
\(\text{lca} \to v\) 考虑树剖，我们只需要对 \(O(\log n)\) 段设计 \(O(\log n)\) 的算法即可。
对每段保存这一段内最浅的每种颜色的位置，这可以开 vector 记录 \(O(\log n)\) 查找。空间复杂度 \(O(n)\)。
没有就跳到下一条链；有就直接到那个位置，随后问题就转化成这一段内向下不超过末尾的倍增了，用上面的方法仍然 \(O(\log n)\) 解决。
最后到 \(v\) 所在的一段仍然作不超过 \(v\) 的倍增即可。
总时间复杂度 \(O(n \log n + q \log^2 n)\)。可以通过离线处理等得到更优的做法。
代码挂了。
T2 尼特（nit）
……还是有些地方不理解。
考虑一个 dp。我们设 \(f(i, j)\) 为只考虑前 \(i\) 个字符时，最大匹配数和当前匹配数之差为 \(j\) 的串个数，\(g(i, j)\) 为对应的匹配数之和。这样设计时如果新增一个字符的贡献时可以直接让 \(f\) 对 \(g\) 贡献得到。
这时可以得到答案就是
\[\frac{\sum_{i\ge 0}g({n, i})}{m^{n - 1}}
\]
\]
转移考虑分类讨论。
- \(S[i] = S[i + 1]\)
\(f(i + 1, j) \leftarrow f(i, j) \times m\)
\(g(i + 1, j)\leftarrow g(i, j)\times m + f(i, j)\) - \(S[i] \neq S[i + 1]\)
\(f(i + 1, 0) = f(i, 0) \times (m - 1) + f(i, 1)\)
\(g(i + 1, 0) = g(i, 0) \times (m - 1) + g(i, 1) + f(i, 1)\)
\(j > 0\) 时：
\(f(i + 1, j) = f(i, j) \times (m - 2) + f(i, j - 1) + f(i, j + 1)\)
\(g(i + 1, j) = g(i, j) \times (m - 2) + g(i, j - 1) + g(i, j + 1) + f(i, j - 1)\)
我们可以得到 \(O(n^2)\) 的做法。考虑优化。
我们能将 \(f, g\) 转移的构造映射到一个满足交换律的结构上，这也表明两次转移的顺序是可以交换的。第一类转移等价于等比数列求和，我们不妨先考虑第二类转移如何做。
观察 \(f\) 的形式，我们不妨推广为维护如下数列：
\[f(i, j) = \left \{
\begin{aligned}
&af(i - 1, j - 1) + bf(i - 1, j) + cf(i - 1, j + 1)\quad &j > 0 \\
&(a + c) f(i - 1, j + 1) + bf(i - 1, j) \quad & j = 0
\end{aligned}
\right.\]
\begin{aligned}
&af(i - 1, j - 1) + bf(i - 1, j) + cf(i - 1, j + 1)\quad &j > 0 \\
&(a + c) f(i - 1, j + 1) + bf(i - 1, j) \quad & j = 0
\end{aligned}
\right.\]
初值有 \(f(0, 0) = 1\)。
我们需要注意的就是当 \(j = 0\) 时的特殊处理。这里可以看作是将系数作了折叠，那我们不妨展开观察。具体地，我们设一个序列
\[\{f(n, n), f(n, n - 1) ,\cdots, f(n, 1) , f(n, 0), f(n, 0), f(n, 1) ,\cdots, f(n, n - 1), f(n, n)\}
\]
\]
的生成函数为 \(F_n(x)\)。不难发现我们可以将数列描述为 \(F_n(x) = F_{n - 1}(x) \times (a + bx + cx^2)\)。因此我们能写出
\[F_n(x) = (a + bx + cx^2)^n(1 + x)
\]
\]
在这题中我们能得到 \(f\) 的生成函数即为 \(F_n(x) = (1 + x)(1 + (m - 2)x + x^2)^n\)。
\(g\) 的生成函数有些不好求。但我们仍能退而求其次，近似地构造 \(n\times F_{n - 1}(x)\)。
然后观察可以发现，\(g(n, i)\) 的值即为 \(n\times [x^i] F_{n - 1}(x)\) 的值加上 \(f(n, 0)\sim f(n, i - 2)\) 中第二维奇偶性和 \(i\) 相同的部分的值。
这点可以感性地从贡献方式上理解。
因此我们的任务变成了提取 \(F = (1 + (m - 2)x + x^2)^n\) 的每一项系数。
不难看出这个微分有限，因此写出 \(F\) 的 ODE：
\[F' = n(1 + (m - 2)x + x^2)^{n - 1} (m - 2 + 2x) = n\frac{F(m - 2 + 2x)}{1 + (m - 2)x + x^2}
\]
\]
也就是
\[(1 + (m - 2)x + x^2) F' = n(m - 2 + 2x)F
\]
\]
两边提取 \(x^k\) 项系数得到
\[(k + 1)F[k + 1] + k(m - 2)F[k] + (k - 1)F[k - 1] = n(m - 2)F[k] + 2nF[k - 1]
\]
\]
也就是
\[k F[k] = (n - k + 1)(m - 2)F[k - 1] + (k - 2 + 2n)F[k - 2]
\]
\]
然后就可以 \(O(n)\) 地递推了。可以知道 \(F[0] = 1, F[1] = n(m - 2)\)。
做完第一类转移后就可以自然得到第二类转移的写法了。
总时间复杂度 \(O(n)\)。
code
// ubsan: undefined
// accoders
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>; using vi = vector<int>; using vp = vector<pii>; using ll = long long;
using ull = unsigned long long; using db = double; using ld = long double; using lll = __int128_t;
template<typename T1, typename T2> T1 max(T1 a, T2 b) { return a > b ? a : b; }
template<typename T1, typename T2> T1 min(T1 a, T2 b) { return a < b ? a : b; }
#define multi int T; cin >> T; while ( T -- )
#define timer cerr << 1. * clock() / CLOCKS_PER_SEC << '\n';
#define iot ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
#define eb emplace_back
#define pb pop_back
const int N = 1e7 + 10;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fll;
int n, m, a[N], ans, pwk, nrm, F[N], G[N];
// int mod;
// const int mod = 10007;
// const int mod = 469762049, g = 3;
const int mod = 998244353; // const int g = 3;
// const int mod = 1004535809, g = 3;
// const int mod = 1e9 + 7;
// const int mod = 1e9 + 9;
// const int mod = 1e9 + 3579, bse = 131;
/* add / sub */ template<typename T1,typename T2>T1 add(T1 a,T2 b){return(a+=b)>=mod?a-mod:a;}template<typename T1,typename...Args>T1 add(T1 a,Args...b){return add(a,add(b...));}template<typename T1,typename T2>T1 sub(T1 a,T2 b){return(a-=b)<0?a+mod:a;}template<typename T1,typename...Args>T1 sub(T1 a,Args...b){return sub(a,add(b...));}template<typename T1,typename T2>void addi(T1&a,T2 b){(a+=b)>=mod?(a-=mod):true;}template<typename T1,typename...Args>void addi(T1&a,Args...b){addi(a,add(b...));}template<typename T1,typename T2>void subi(T1&a,T2 b){(a-=b)<0?(a+=mod):true;}template<typename T1,typename...Args>void subi(T1&a,Args...b){subi(a,add(b...));}
/* Fastmod / mul */ struct FastMod{int m;ll b;void init(int _m){m=_m;if(m==0)m=1;b=((lll)1<<64)/m;}FastMod(int _m){init(_m);}int operator()(ll a){ll q=((lll)a*b)>>64;a-=q*m;if(a>=m)a-=m;return a;}}Mod(mod);int mul(int a,int b){return Mod(1ll*a*b);}template<typename T1,typename T2>int mul(T1 a,T2 b){return Mod((long long)(1ll*a*b));}template<typename T,typename...Args>int mul(T a,Args...b){return mul(a,mul(b...));}template<typename T1,typename T2>void muli(T1&a,T2 b){a=Mod(1ll*a*b);}template<typename T1,typename...Args>void muli(T1&a,Args...b){muli(a,mul(b...));} // /* trivial multiple function(idk whether its useful*/ int mul(int a, int b) { return 1ll * a * b % mod; } template <typename T1, typename T2> int mul(T1 a, T2 b) { return (long long)(1ll * a * b) % mod; } template <typename T, typename ...Args> int mul(T a, Args ...b) { return mul(a, mul(b...)); }
/* qp fac C */ template<typename T1,typename T2>T1 qp(T1 a,T2 b){T1 ret=1;for(;b>0;a=1ll*a*a%mod,b>>=1)if(b&1)ret=mul(ret,a);return ret;}vi __fac({1,1}),__ifc({1,1}),__inv({0,1});inline void ___prep(int n){static int i=2;if(i<n)for(__fac.resize(n),__ifc.resize(n),__inv.resize(n);i<n;i++)__fac[i]=mul(i,__fac[i-1]),__inv[i]=mul((mod-mod/i),__inv[mod%i]),__ifc[i]=mul(__inv[i],__ifc[i-1]);}inline int fac(int x){return ___prep(x+1),__fac[x];}inline int ifc(int x){return ___prep(x+1),__ifc[x];}inline int inv(int x){return ___prep(x+1),__inv[x];}inline int C(int n,int m){if(n<m or n<0 or m<0)return 0;return mul(fac(n),ifc(m),ifc(n-m));}
// /* sum of i^k */ int S(int n,int k){vector<int>__pre(k+4),__suf(k+4),__pw(k+4),__pri(k+4);vector<bool>__vis(k+4,0);__pw[1]=1;for(int i=2,cnt=0;i<=k+2;++i){if(!__vis[i])__pri[++cnt]=i,__pw[i]=qp(i,k);for(int j=1;j<=cnt and i*__pri[j]<=k+2;++j){__vis[i*__pri[j]]=1;__pw[i*__pri[j]]=mul(__pw[i],__pw[__pri[j]]);if(i%__pri[j]==0)break;}}rep(i,2,k+2)__pw[i]=add(__pw[i],__pw[i-1]);__pre[0]=__suf[k+3]=1;rep(i,1,k+2)__pre[i]=mul(__pre[i-1],(n-i+mod));pre(i,k+2,1)__suf[i]=mul(__suf[i+1],(n-i+mod));int tmp=0,ret=0;rep(i,1,k+2){if((k-i)&1)subi(ret,mul(__pw[i],__pre[i-1],__suf[i+1],ifc(i-1),ifc(k+2-i)));else addi(ret,mul(__pw[i],__pre[i-1],__suf[i+1],ifc(i-1),ifc(k+2-i)));}return ret;}
// /* inv 2/3/6 / phi */ constexpr int __var_pow(int a, int b) { int ret = 1; for (; b > 0; b >>= 1, a = 1ll * a * a % mod) if (b & 1) ret = 1ll * ret * a % mod; return ret; } constexpr int __var_phi(int x) { if (x <= 2) return 1; int ret = x; for (int i = 2; 1ll * i * i <= x; ++i) if (x % i == 0) { ret = ret / i * (i - 1); while (x % i == 0) x /= i; } if (x > 1) ret = ret / x * (x - 1); return ret; } const int __phi_mod = __var_phi(mod); const int inv2 = __var_pow(2, __phi_mod - 1), inv3 = __var_pow(3, __phi_mod - 1), inv6 = __var_pow(6, __phi_mod - 1);
void ode(int a[], int n) {
a[0] = 1, a[1] = mul(m - 2 + mod, n);
rep(i,2,2*n+1) {
a[i] = add(mul(a[i - 1], m - 2 + mod, n - i + 1 + mod), mul(a[i - 2], 2 * n - i + 2));
muli(a[i], inv(i));
}
}
signed main() {
cin >> n >> m;
rep(i,1,n) cin >> a[i];
rep(i,1,n - 1) {
if (a[i] != a[i + 1]) ++ pwk;
else ++ nrm;
}
if (pwk) ode(F, pwk), ode(G, pwk - 1);
else F[0] = 1;
pre(i,pwk,1) addi(F[i], F[i - 1]);
pre(i,pwk,1) addi(G[i], G[i - 1]);
rep(i,0,pwk) muli(G[i], pwk);
int s[2] = { 0, 0 };
rep(i,2,pwk) addi(s[i & 1], F[i - 2]), addi(G[i], s[i & 1]);
if (nrm > 0) {
rep(i,0,pwk)
G[i] = add(mul(m, G[i]), mul(nrm, F[i]));
}
rep(i,0,pwk) addi(ans, G[i]);
if (nrm > 0) muli(ans, qp(m, nrm - 1));
cout << mul(ans, qp(m, 1ll * (n - 1) * (mod - 2) % (mod - 1))) << '\n';
}
