P14816 [ICPC 2023 Yokohama R] Ferris Wheel 题解
给定 \(n,k\)，求有多少种给大小为 \(2n\) 的环的每个点染上 \([1,k]\) 的颜色的方案，满足：
- 存在一种将所有点两两配对的方式，使得每一对点的颜色相同，并且如果在每对匹配的点间连一条线段，这些线段两两不交。
两种方案相同，当且仅当它们在某种旋转下重合。
答案对 \(998244353\) 取模。\(n,k\le 3\times 10^6\)。
先考虑如何判断一个方案是否合法，可以发现一定有一条线段连接了两个相邻的点（可以任意找一条线段，这条线段会将环分成两部分，一直递归下去直到找到两个相邻点间的线段），于是我们可以将这对点删去，并继续找下一组相邻点间的匹配，所以一个方案一定可以通过不断删除相邻两个颜色相同的点将环删空。并且这也是充要条件，每次在删除的两个点间连一条线段就能构造出一种方案。
考虑如果没有旋转同构这个条件怎么做，断环成链，两个问题条件依然等价，即一个序列合法当且仅当能通过不断删除相邻两个颜色相同的元素将序列删空。删相邻两个颜色相同的元素很像括号序列，如果将每次删除两个元素看成一对左右括号，那么每种删除方式都对应了一种括号序列，考虑将每种染色方案都唯一对应到一个括号序列上并对这个括号序列计数。
用栈来模拟括号匹配过程，即初始有个空栈，依次枚举每个元素，如果和栈顶颜色相同就进行匹配，否则压入栈中。此时每种方案就唯一对应了一种括号序列，对这种括号序列计数，那么一个括号序列满足条件当且仅当每个元素压入栈中时与栈顶颜色不同，即每个左括号颜色与上一层的左括号颜色不同。枚举每种括号序列，设一个括号序列有 \(m\) 个在第一层的左括号，那么贡献为 \(k^m(k-1)^{n-m}\)。
枚举 \(m\)，考虑计数有多少个括号序列长度为 \(n\) 且长成 \((S_1)(S_2)\ldots(S_m)\) 的形式，其中 \(S_i\) 是一个合法括号序列，记上述答案为 \(g(m,n)\)，可以构造双射变为计数形如 \((\ldots ((S_1)S_2)\ldots )S_m\) 的括号序列数量，相当于在网格上从 \((m-1,0)\) 走到 \((\frac n 2-1,\frac n 2-1)\) 并且不跨过 \(y=x\) 这条直线的方案数，用反射容斥可得 \(g(m,n) = {n-m-1\choose \frac n 2-m}-{n-m-1\choose \frac n 2-m-1}\)。于是答案就是：
回到原问题，旋转同构显然要用 Polya 定理，设 \(f(n)\) 表示有多少个满足条件的序列存在长度为 \(n\) 的循环节，那么答案为 \(\sum\limits_{i=0}^{2n-1}f(\gcd(i,2n)) = \sum\limits_{d\mid n}f(d)\varphi(\frac{2n}d)\)。考虑求 \(f(n)\)，如果 \(n\) 为偶数则与上述问题相同，如果 \(n\) 为奇数那么不断删除相邻两个颜色相同的元素后还会剩下一些元素。而由于可以在相邻两个循环节之间删除相当于可以不断删去序列首尾颜色相同的元素，要求最终恰好剩下一个元素，也就是说要求剩下的元素是回文的。
还是将每种合法的颜色序列唯一对应到一个括号序列上，那么括号序列会有一些未匹配的左括号，要求这些左括号的颜色回文，设有 \(m\) 个在第一层的左括号，贡献为 \(k^m(k-1)^{\frac{n+1}2-m}\)。考虑计数这样的括号序列数，再枚举除了第一个未匹配的左括号外有多少个未匹配的左括号，设有 \(j\) 个，那么就是计数有多少个形如 \((S_1)\ldots(S_{m-1})(S_m(S_{m+1}\ldots(S_{m+j}\) 的括号序列，即 \(g(m+j,n+j+1)\)，答案为：
即：
那么 \(f(n)\) 可以在 \(\mathcal{O}(n)\) 的时间内计算，总复杂度即为 \(\mathcal{O}(\sigma(2n))\)，显然不超过 \(\mathcal{O}(n\log n)\)。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
using namespace std;
const int N = 8e6+5,mod = 998244353;
int p[N],phi[N],n,k,cnt;
ll pw1[N],pw2[N],fac[N],inv[N],ans;
inline ll C(int n,int m){return n<m||m<0?0:fac[n]*inv[m]%mod*inv[n-m]%mod;}
inline ll qp(ll x,ll y = mod-2)
{ll s = 1;for(;y;y >>= 1,x = x*x%mod)if(y&1)s = s*x%mod;return s;}
inline ll F(int n)
{ll s = 0;if(n&1)for(int i = 1;i <= (n+1)/2;i++)(s += pw1[i]*pw2[(n+1)/2-i]%mod*C(n-i,(n+1)/2-i)) %= mod;else for(int i = 1;i <= n/2;i++)(s += pw1[i]*pw2[n/2-i]%mod*(C(n-i-1,n/2-i)-C(n-i-1,n/2-i-1))) %= mod;return s;
}
char buf[1<<21],*p1,*p2;
inline int rd()
{char c;int f = 1;while(!isdigit(c = getchar()))if(c=='-')f = -1;int x = c-'0';while(isdigit(c = getchar()))x = x*10+(c^48);return x*f;
}
int main()
{// freopen(".in","r",stdin);// freopen(".out","w",stdout);n = rd()<<1;k = rd();pw1[0] = pw2[0] = phi[1] = fac[0] = inv[0] = inv[1] = 1;for(int i = 2;i <= n;i++)inv[i] = (mod-mod/i)*inv[mod%i]%mod;for(int i = 1;i <= n;i++){fac[i] = fac[i-1]*i%mod;(inv[i] *= inv[i-1]) %= mod;pw1[i] = pw1[i-1]*k%mod;pw2[i] = pw2[i-1]*(k-1)%mod;}for(int i = 2;i <= n;i++){if(!phi[i])p[++cnt] = i,phi[i] = i-1;for(int j = 1;j <= cnt&&i*p[j] <= n;j++){if(i%p[j] == 0){phi[i*p[j]] = phi[i]*p[j];break;}phi[i*p[j]] = phi[i]*(p[j]-1);}}for(int i = 1;i <= n;i++)if(n%i == 0)(ans += phi[n/i]*F(i)) %= mod;cout << (ans+mod)*qp(n)%mod << endl;return 0;
}