hdu 2068（错排+组合）水题

小鱼儿 2023-06-09 10:04 5阅读 0赞

# hdu 2068（错排+组合）水题 #

[题目链接][Link 1]

以前做过一次，开始没做出来，这次做的话，感觉还是比较水的，就是错排加上组合公式就可以了

错排公式：**f\[n\]=(n-1)\*(f\[n-1\]+f\[n-2\]);**

组合公式：

c[0]=1;
    /**组合公式（递推实现）*/
    for(int i=1;i<=n;i++){
        
    	c[i]=c[i-1]*(n-i+1)/i;、
    }

由于题目说只要答对一半或以上即可，于是只要求下和即可：

于是代码如下：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #define ll long long
    using namespace std;
    ll f[30];
    ll c[30];
    int main(){
        
        f[0]=1;
        f[1]=0;
        f[2]=1;
        /**全错排公式*/
        for(int i=3;i<=25;i++){
        
            f[i]=(f[i-1]+f[i-2])*(i-1);
        }
        int n;
        while(~scanf("%d",&n)){
        
            if(n==0)
                break;
            memset(c,0,sizeof(c));
            c[0]=1;
            /**组合公式（递推实现）*/
            for(int i=1;i<=n;i++){
        
                c[i]=c[i-1]*(n-i+1)/i;
            }
            ll sum=0;
            int m;
            for(int i=0;i<=n/2;i++){
        
                sum+=c[n-i]*f[i];
            }
            printf("%lld\n",sum);
        }
        return 0;
    }

其中hdu 2049也是一道有关错排的题。。。。

[题目链接][Link 2]

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=2068
[Link 2]: http://acm.hdu.edu.cn/showproblem.php?pid=2049

发表评论取消回复

表情：

评论列表（有 0 条评论，5人围观）

还没有评论，来说两句吧...

相关阅读

相关 hdu 2068（错排+组合）水题

hdu 2068（错排+组合）水题 [题目链接][Link 1] 以前做过一次，开始没做出来，这次做的话，感觉还是比较水的，就是错排加上组合公式就可以了错排公式：f

小鱼儿/ 2023年06月09日 10:04/ 0 赞/ 6 阅读

相关 HDU 1326(水题)

include <iostream> include <cstdio> using namespace std;

你的名字/ 2022年09月20日 12:43/ 0 赞/ 232 阅读

相关 HDU 1303(水题)

include<stdio.h> define N 20 int A[N]; int main() {

落日映苍穹つ/ 2022年09月20日 12:43/ 0 赞/ 250 阅读

相关 HDU 1259(水题)

include<iostream> using namespace std; int main() { in

淡淡的烟草味﹌/ 2022年09月20日 12:41/ 0 赞/ 203 阅读

相关 HDU 1237(水题)

include <iostream> include <cstdio> include <cstring> using namespace

快来打我*/ 2022年09月20日 11:28/ 0 赞/ 196 阅读

相关 HDU 1170(水题)

题意：如题。 include <iostream> include <iomanip> using namespace std;

今天药忘吃喽~/ 2022年09月20日 11:23/ 0 赞/ 101 阅读

相关 HDU 1157(水题)

题意：求给定一排数的排序之后的中点。 include<stdio.h> include<stdlib.h> include<algorithm>

心已赠人/ 2022年09月20日 11:22/ 0 赞/ 111 阅读

相关 HDU 1128(水题)

题意：如题。 include<stdio.h> include<memory.h> define N 1000001 int visit

亦凉/ 2022年09月20日 11:17/ 0 赞/ 155 阅读

相关错排问题错排公式 Hdu 1465 + 2048 +2049 + 2068 + 4535

也称伯努利-欧拉装错信封问题 n错排公式：F\[n\]=(n-1)\(F\[n-1\]+F\[n-2\]) 证明： 1.当前n-1个错排时：将其任意一封信与n对调,共(

小鱼儿/ 2022年08月25日 10:52/ 0 赞/ 156 阅读

相关 HDU-前进（水题）

前进 Problem Description 轻松通过墓碑，进入古墓后，才发现里面别有洞天。突然，Yifenfei发现自己周围是黑压压的一群蝙蝠

向右看齐/ 2022年05月26日 04:22/ 0 赞/ 235 阅读