首先把 $1\sim 2N+K$ 分为 $L=[1,N],R=(N,N+K],M=(N+K,2N+K]$ 三类，要求不能出现 $LL$ 和 $RR$。对于有 $p$ 个 $L$，$q$ 个 $r$，$s$ 个 $M$ 的字符串 $c$，对应的合法序列数为 $\frac{n!n!k!}{(n-p)!(n-q)!(n-s)!}$。考虑先计数 $c$，整个序列被 $M$ 切成了 $s+1$ 段，每段固定是 $LRLRL\dots$ 或 $RLRLR\dots$。设一段有 $x$ 个 $L$ 和 $y$ 个 $R$，那么方案数的 GF 为 $$G(x,y)=1+x+y+2xy+x^2y+xy^2+2x^2y^2+\dots=1+(x+y+2xy)(1+xy+x^2y^2+\dots)=1+\frac{x+y+2xy}{1-xy}$$ $$=\frac{(1+x)(1+y)}{1-xy}$$ 那么合法 $c$ 的方案数即需要求 $[x^py^q]G(x,y)^{s+1}$。而 $$(1+x)^{s+1}=\sum\binom{s+1}ix^i$$ $$(1+y)^{s+1}=\sum\binom{s+1}iy^i$$ $$(1-xy)^{-(s+1)}=\sum\binom{s+i}ix^iy^i$$ 所以方案数为 $$\sum\limits_i\binom{s+1}{p-i}\binom{s+1}{q-i}\binom{s+i}i$$ 而由于 $p-i\le s+1,q-i\le s+1$，所以 $i\ge\max(p-s-1,q-s-1),i\le\min(p,q)$，$i$ 的枚举量是 $\mathcal{O}(s)$ 的，同时由于 $|p-q|\le s+1,p+q=N-s$，所以 $p$ 的枚举量也是 $\mathcal{O}(s)$ 的，总时间复杂度 $\mathcal{O}(N+K^3)$。