UOJ Logo LFYZ Online Judge

LFYZOJ

#50. 【2018年2月期末欢乐赛】信件

统计

问题描述

秋穰子给秋静叶写信。

秋穰子写了 $n$ 封信,她每封信的信纸和信封都是有搭配的。然而,她惊奇地发现,她每封信的信纸和信封都搭配错了。

问你有多少种全部搭配错的方案。

输入格式

一个整数 $n$。

输出格式

一个整数,是全部搭配错的方案种数。

样例一

input

2

output

1

数据范围与约定与提示

对于 $100\%$ 的数据,$n \leq 45$。

错位排列递推式: $$f_n=(n-1)(f_{n-1}+f_{n-2}).$$

时间限制: $1\mathrm{s}$

内存限制: $256\mathrm{MB}$