糊涂人寄信——组合数学

糊涂人寄信——组合数学

题目描述

有一个糊涂人，写了 n 封信和 n 个信封，到了邮寄的时候，把所有的信都装错了信封。求装错信封可能的种类数。

输入描述

有多行读入，每行输入一个正整数 n，表示一种情况。(n≤20)

输出描述

输出相应的答案。

输入输出样例

示例

输入

1
3
4

输出

0
2
9

运行限制

• 最大运行时间：1s

• 最大运行内存: 256M

#include <iostream>
using namespace std;
int main()
{long long dp[20];//必须用long long 型dp[0]=dp[1]=0;dp[2]=1;for(int i=3;i<=20;i++){dp[i]=(i-1)*(dp[i-1]+dp[i-2]);}int n;while(cin>>n){cout<<dp[n]<<endl;}return 0;
}