洛谷P1595 信封问题
程序员文章站
2022-06-19 10:46:29
题目描述 某人写了n封信和n个信封,如果所有的信都装错了信封。求所有信都装错信封共有多少种不同情况。 输入输出格式 输入格式: 一个信封数n(n<=20) 输出格式: 一个整数,代表有多少种情况。 输入输出样例 输入样例#1: 复制 2 输出样例#1: 复制 1 输入样例#1: 复制 2 输出样例# ......
题目描述
某人写了n封信和n个信封,如果所有的信都装错了信封。求所有信都装错信封共有多少种不同情况。
输入输出格式输入格式:
一个信封数n(n<=20)
输出格式:
一个整数,代表有多少种情况。
输入输出样例 输入样例#1: 复制
2输出样例#1: 复制
1输入样例#2: 复制
3输出样例#2: 复制
2
递推公式:$f[n]=(n-1)*(f[n-1]+f[n-2])$
#include<iostream> #include<cstdio> using namespace std; int main() { int N; cin>>N; int a1=0,a2=1,a3; for(int i=3;i<=N;i++) { a3=(i-1)*(a1+a2); a1=a2,a2=a3; } if(N==1) cout<<a1; else if(N==2) cout<<a2; else cout<<a3; return 0; }