题意
令 \(p\) 是一个 \(1\dots n\) 的排列，记 \(f(p)=|\{p_i-p_{(i\bmod n)+1}|1\le i\le n\}|\)，即 \(p_i-p_{(i\bmod n)+1}\) 中不同数的个数。
给定 \(n,m,s,t\)，设 \(w=\min\{f(p)|p\in \operatorname{perm}(1\dots n)\}\)（也就是对于所有 \(1\dots n\) 的排列 \(p\)，\(f(p)\) 的最小值），求有多少 \(p\) 满足 \(f(p)=w,p_1=s,p_m=t\)。
\(2\le m\le n\le10^{12}\)。
题解
设 \(a_i=p_i-p_{(i\bmod n)+1}\in\{x,-y\}\)，\(x,y\in[1,n)\)。接下来考虑 \(x,y\) 的性质。
显然 \(\gcd(x,y)=1\)。\(\sum_{i=1}^n a_i=0\)，设有 \(t\) 个 \(x\)，则 \(tx-(n-t)y=0\)，可得 \(t=\frac{ny}{x+y}\)，于是 \(x+y|n\)。
每 \(x+y\) 个看成一块，设其中有 \(t\) 个 \(x\)，和为 \(tx-(x+y-t)y=(t-y)(x+y)\)，为 \(x+y\) 倍数。而将这区间向左或向右平移一单位，和会变化 \(x+y,-x-y\) 或 \(0\)。而所有块的和为 \(0\)，则必有一个区间和为 \(0\)，则不是排列。但当 \(x+y=n\) 时是例外。于是可知 \(x+y=n\)。
此时 \(p\) 是 \(\bmod n\) 意义下的等差数列。公差设为 \(x\)，则转化为求 \(x(m-1)\equiv t-s\pmod n\wedge\gcd(x,n)=1\)。对前面的方程，解可表示为 \(x_0+k\frac{n}{d}\)，\(d=\gcd(m-1,n)\)，\(x_0\in[0,\frac{n}{d})\)，\(k\in[0,d)\)。对后面的条件，对 \(n\) 的所有质因子容斥即可。复杂度 \(O(\sqrt n+2^{w(n)}\log n)\)。