极简·递推

这是老师上课讲的例题之一，也是一道特典型的递推。
在放代码之前，我们先求出公式：
一封信时结果为$0$种可能性，两封信时结果为$1$种，三封信时$2$种……你可以再多推算几步，得知如果索引从$1$开始，在减少一封信后，将得出$i-1$封完全错排的信及最后一封位置正确的信，交换前面的任意一封信和最后一封即可。去掉两封信后同理，最终可得$a[i]=(a[i-1]+a[i-2])*(i-1)$，注意接下来我的代码中索引从0开始，因此略有改动。

---

不想听的话，注释里也有思路的大致解析，当然肯定没有自己想来的效果。

#include<iostream>//我要挑战最短题解的代码
using namespace std;
long long n,a[25];//不开long long见祖宗，20个还是不排除爆int的
int main(){//时间复杂度O(n)，不过分吧
    cin>>n,a[0]=0,a[1]=1;//极简赋值，请勿模仿
    for(int i=2;i<n;i++) a[i]=i*(a[i-1]+a[i-2]);//如果你从1开始，此处的i请改为(i-1)
    cout<<a[n-1];
    return 0;
}