题意是说在长度为 n 的环排列中，按照一定的方向（顺时针或逆时针），后一个数不能仅比前一个数大 1 ， n 的下一个数不能是 1 ，问这种长度为 n 且本质不同（本质不同指环上数字的相对位置不同，如 1234 和 2341，3412，4123 都是本质相同的）的环有多少种。
分析样例，使用公式：
a(n) = (n-2) * a(n-1) + (n-1) * a(n-2) - (-1) ^ n ，打表解决。
代码如下：
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int mod = 998244353; 4 __int64 w[100001]; 5 int main() 6 { 7 int t,n; 8 scanf("%d",&t); 9 w[1] = 0; 10 w[2] = 0; 11 w[3] = 1; 12 w[4] = 1; 13 for(int i = 5; i < 100001; i++) 14 { 15 w[i] = (w[i-1]*(i-2)%mod + ((i-1)*w[i-2]%mod))%mod; 16 if(i&1) w[i]++; 17 else w[i]--; 18 w[i]%=mod; 19 } 20 while(t--) 21 { 22 scanf("%d",&n); 23 printf("%I64d\n",w[n]); 24 } 25 return 0; 26 }
打表还可以使用公式：
a(n) = (n-3) * a(n-1) + (n-2) * (2*a(n-2) + a(n-3))
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int mod = 998244353; 4 __int64 w[100001]; 5 int main() 6 { 7 int t,n; 8 scanf("%d",&t); 9 w[1] = 0; 10 w[2] = 0; 11 w[3] = 1; 12 for(int i = 4; i < 100001; i++) 13 { 14 w[i] = (i-3) * (w[i-1]%mod)%mod + (i-2) * ((2*w[i-2]%mod + w[i-3]%mod)%mod)%mod; 15 w[i]%=mod; 16 } 17 while(t--) 18 { 19 scanf("%d",&n); 20 printf("%I64d\n",w[n]); 21 } 22 return 0; 23 }
原文：https://www.cnblogs.com/Taskr212/p/9519920.html
