思维路径
根据映射，我们可以发现数字的规律必定是两两互换，即若 \(f_a\) 是 \(b\) ，那么 \(f_b\) 一定是 \(a\) 。
我们可以通过手算 \(1\) 到 \(4\) 的数据，观察规律。
观察第 \(4\) 行的数据。
-
以 \(1\) 为始的数据后面跟的三个数据正好与第三行的顺序相同。方案数和第三行的方案数相同。
-
不以 \(1\) 为始得数据，以 \(2\) 为例，也就是 \(1\) 和 \(2\) 互换了位置，剩下 \(2\) 个数字正好和第二行得数据相同，方案数与第二行得方案数相同，这样的数字有 \(4-1\) 个
得出结论：第 \(i\) 行的数据等于第 \(i-1\) 行加上第 \(i-2\) 行乘以 \(i-1\)。即：
\[f_i=f_{i-1}+(i-1) \times f_{i-2}
\]
代码实现
空间很小，需要使用滚动数组，第 \(i\) 位的储存方式如下。
if((i&1)==0){
f[0]*=i-1;
f[0]%=MOD;
f[0]+=f[1];
f[0]%=MOD;
}
else{
f[1]*=i-1;
f[1]%=MOD;
f[1]+=f[0];
f[1]%=MOD;
}
同时注意要取模。
AC 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=14233333;
ll n,f[2];
void input(){
cin>>n;
}
void solve(){
f[1]=1; f[0]=2;
for(ll i=3;i<=n;i++){
if((i&1)==0){
f[0]*=i-1;
f[0]%=MOD;
f[0]+=f[1];
f[0]%=MOD;
}
else{
f[1]*=i-1;
f[1]%=MOD;
f[1]+=f[0];
f[1]%=MOD;
}
}
cout<<f[n&1];
}
int main(){
input();
solve();
return 0;
}