首页 > 代码库 > codevs 1697 ⑨要写信

codevs 1697 ⑨要写信

传送门

1697 ⑨要写信

 时间限制: 1 s
 空间限制: 128000 KB
 题目等级 : 黄金 Gold
题目描述 Description

琪露诺(冰之妖精)有操控冷气的能力。能瞬间冻结小东西,比普通的妖精更危险。一直在释放冷气的她周围总是非常寒冷。

由于以下三点原因……

  • 琪露诺的符卡 冰符“Icicle Fall”-Easy的弹幕有够蠢的,只要站在她的正前方就没任何弹幕会碰到你;
  • ZUN在《红魔乡》中介绍她时已经说她有点笨笨的了;
  • 在ZUN放出《东方花映冢》的介绍图时,在图中把琪露诺放在了⑨的位置上,并以“⑨笨蛋”简单带过,从此“⑨”及“笨蛋”就成为她的别名了……

所以琪露诺便得到了“笨蛋”的别称。

某日,琪露诺又2了……

她写了N封信要装到N个信封里面,却全都装错了……现在想知道有多少种装错的可能性。

输入描述 Input Description

信和信封的数量N。

输出描述 Output Description

装错的可能性的数量。

样例输入 Sample Input

输入样例1

 

2

 

输入样例2

 

4

 

样例输出 Sample Output

输出样例1

 

1

 

输出样例2

 

9

 

数据范围及提示 Data Size & Hint

1≤N≤100

【题目大意】n封信错排。

【思路】错排问题。递推公式。

f[n]表示n封信错排的可能数。

证明:现在要对第n封信进行错排,有n-1个位置可以选择。假设选择位置k。

对位置k原有的信进行错排,有两种情况。

(1)到位置n,那么n,k已经错排好了,再加上剩下n-2封信的错排,f[n-2]。

(2)k没有放到位置n,+f[n-1].

分步乘法计数原理和分类加法计数原理 

f[n]=(n-1)*(f[n-2]+f[n-1]);

【code】

#include<iostream>
#include<cstdio>
using namespace std;
int n,f[120];
long long dp(int n)
{
    if(n==1)return 0;
    if(n==2)return 1;
    else
    return (n-1)*(dp(n-1)+dp(n-2));
}
int main()
{
    scanf("%d",&n);
    printf("%lld\n",dp(n));
    return 0;
}

没写高精会T。 ToT~~

codevs 1697 ⑨要写信