首页 > 代码库 > 洛谷P1595 信封问题
洛谷P1595 信封问题
P1595 信封问题
最新讨论
- = =
题目描述
某人写了n封信和n个信封，如果所有的信都装错了信封。求所有信都装错信封共有多少种不同情况。
输入输出格式
输入格式：
一个信封数n
输出格式：
一个整数，代表有多少种情况。
输入输出样例
输入样例#1：
样例1：2样例2：3
输出样例#1：
样例1：1样例2：2
题解：
错位排列
本题解用的是f(n)=(n-1)*(f(n-1)+f(n-2))
这道题的另一个公式 ans=n!(1-1/1!+1/2!-1/3!+...+(-1)^n*(1/n!))
AC代码：
#include<cstdio>#include<cstring>#include<iostream>using namespace std;#define N 1010int n;long long dfs(int x){ if(x==0) return 1; if(x==1) return 0; if(x==2) return 1; if(x==3) return 2; if(x==4) return 9; return (x-1)*(dfs(x-1)+dfs(x-2));}int main(){ scanf("%d",&n); printf("%lld",dfs(n)); return 0;}
洛谷P1595 信封问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。