递推总结
错排公式
介绍
问题：现有10本书按照顺序摆放，现要求重新排列，使得新的书的顺序中每一本书都不在原来的位置，求有多少种排列方式？
这个问题推广一下，就是错排问题，是组合数学中的问题之一。考虑一个有n个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。 n个元素的错排数记为D(n)。 研究一个排列错排个数的问题，叫做错排问题或称为更列问题。
OK，现在详细分析这个问题，我们要的最终结果就是书的编号与所在位置的编号不同，在这里，我们把n本书的错排操作数记为D(n)，那n-1本就是D(n-1)，n-2本就是D(n-2)啦，下面，我们把放置问题分为两步（初始位置号与书的编号相同）：
第一步：
- 我们取一本书，书的编号为m，现在这本书就在我们手中，注意，按照题目要求，最开始的时候这本书的位置号也是m号，按照题目要求，我们现在放书时不能放回这个位置m了，而是要选择其他位置，那么有多少种选择呢?
- 想一下，总共有n本书，n个位置，现在我手里这本书不能把它放到位置m，那么剩下的n-1个位置我当然就是随便扔啦，也就是n-1种扔法，好，现在，我选择了位置k，我决定把手里这本书放到位置k这里，记住这个是位置编号k，那么，我肯定要把原来这里的编号为k的书拿出来，再把这本编号为n的书放进去喽。所以，现在我们手里的书的编号是k。
第二步：
我们把手里这本编号为k的书本放到书架，注意，放的过程中我们又面临两种情况，可以想到，此时此刻现在书架上编号m的位置是空着的，所以我们可以选择放在这个位置上，书的编号为k，位置编号为m，没错，满足题意，这是第一种情况，还有一种就是我不选择这个空着的位置m，我再重新选择一个新的位置，我们称之为第二种情况，下面详细分析
第一种情况：我把这本编号为k的书放到这个编号为m的地址，那现在我们面前是什么状况呢，就是位置k和位置m的书交换位置，也就是位置号不等于书号，即满足错排，总共n个位置，我们只动了m和k这两个位置，那么剩下的n-2个位置还是纹丝不动，保持一一对应的关系呢
那么对于剩下的这n-2本书的错排操作，我们又回到了问题的起点，求n-2本的错排操作数D(n-2)，结合第一步，我们可以得到第一种情况总共有(n-1)*D(n-2)种方法
第二种情况：我们不选择这个空着的位置m啦，我们手持这本编号为k的书，我们从除了位置m以及位置k的剩下的n-2个位置中选择一个位置。
OK，我们现在开始想，我手里这本书不能放在这个位置m，嗯嗯，除了第一步我们放置的那本书m不用管了，我们还要搞手里这本和剩下的n-2本，也就是n-1本，同时又要求手里这本k还不能放到位置m，这是不是就相当于把手里这本加上剩下的n-2本也就是n-1本书进行错排呢？
哇哇哇，想一想，错排的定义，要求每本书都不能呆在某一个特定位置，是不是刚好符合呢QWQ，所以，现在的为题就到了求手里这本和剩下的n-2本总共是n-1本书的错排操作数，我们记为D(n-1)，结合第一步，我们得出这第二种情况共有(n-1)*D(n-1)种方法
好的，现在我们总结两种情况，结果进行相加，就可以得到递推公式啦
递推公式为：D(n)=(n-1)*(D(n-1)+D(n-2))
例题
#include<iostream>
#include<algorithm>
using namespace std;
long long func(int n)//计算阶乘
{
long long sum=1;
for(int i=2;i<=n;i++)sum*=i;
return sum;
}
int main()
{
long long f[30]={0};//长整型数组用来存放错误的抽取
f[1]=0;
f[2]=1;
for(int i=3;i<21;i++)f[i]=(i-1)*(f[i-1]+f[i-2]);//递推公式
//以上进行预处理
int c,n;
cin>>c;
while(c--)
{
cin>>n;
double ans=f[n]*100.0/func(n);
printf("%.2f%%\n",ans);//主义输出格式
}
return 0;
}参考
https://blog.csdn.net/bengshakalakaka/article/details/83420150
组合+错排
例题
#include<iostream>
#include<algorithm>
using namespace std;
int c,m,n;
long long f[25];
long long C[25];
int main()
{
f[1]=0;
f[2]=1;
for(int i=3;i<=20;i++)
{
f[i]=(i-1)*(f[i-1]+f[i-2]);
}
C[0]=1;C[1]=1;C[2]=2;
for(int i=3;i<=20;i++)
{
C[i]=C[i-1]*i;
}
cin>>c;
while(c--)
{
cin>>n>>m;
cout<<C[n]/C[m]/C[n-m]*f[m]<<endl;
}
return 0;
}单纯地递推
例题
3、折线分割平面
思路：列举找规律
第1条折线，穿过0条线，多了1个区间；
第2条折线，穿过2条线，多了5个区间；
第3条折线，穿过4条线，多了9个区间；
第4条折线，穿过6条线，多了13个区间；
多的区间: 2*2*(n-1)+1
#include<iostream>
#include<algorithm>
using namespace std;
long long ans[10005]={0,2,7};
int main()
{
for(int i=3;i<10005;i++)ans[i]=ans[i-1]+4*(i-1)+1;
int t,n;
cin>>t;
while(t--)
{
cin>>n;
cout<<ans[n]<<endl;
}
return 0;
}
