组合数学+__int128

技术文章 10个月前 完美者
1,831 0

标签:clip   ==   阶乘   使用   href   getchar   ++   -o   iostream   

今天是Tabris和mengxiang000来到幼儿园的第3天,mengxiang000接到了一个布置会场的任务。
他需要将贵宾观众席的椅子排成一排,一共需要N个。
幼儿园只有两种椅子,所以他也只能使用两种椅子。(A类型和B类型)并且假设每种椅子的数量都是无限的。
而其如果想要摆置一个B类型的椅子,对应就需要必须有连续两个一起布置。换句话说,就是如果出现了B类型的椅子,其必须且只有两个连着B类型的椅子。
mengxiang000突然想知道对应N个椅子排成一列,他能够有多少种布置的方式.

链接:https://ac.nowcoder.com/acm/problem/14345
来源:牛客网

本题包含多组输入第一行输入一个整数t,表示测试数据的组数
每组测试数据包含一行,输入一个整数N,表示一共需要摆放的椅子数量
t<=30
1<=N<=30

输出描述:

每组测试数据输出包含一行,表示一共有多少种布置的方式。
示例1

输入

复制

2
2
4

输出

复制

2
5

说明

第一个样例,AA,BB两种方案。
第二个样例,AAAA,BBBB,AABB,ABBA,BBAA五种方案 对于ABBB 因为有连续3个B类型椅子所以不可行


这个题就是30的阶乘会爆ll ,所以可以用__int128
还有一个知识点就是如果有a个A,b个B,所以答案就是[(a+b)!]/[(a!)*(b!)]


#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e3+100;
void out(__int128 x) {
    if (x < 0) {
        x = -x;
        putchar(-);
    }
    if (x >= 10) out(x / 10);
    putchar(x % 10 +0);
}
void read(__int128 &x) {
    x = 0;
    char ch;
    int flag = 1;
    while (ch = getchar()) {
        if (ch == -) flag = -1;
        if (ch >= 0 && ch <= 9) break;
    }
    x = ch-0;
    while ((ch = getchar()) >= 0 && ch <= 9) {
        x = x*10 + ch-0;
    }
    x *= flag;
}
int main(){ 
    __int128 t,n;
    read(t);
    while(t--){
        read(n);
        __int128 m=n/2+1;
        __int128 ans=0;
        for(__int128 i=0;i<=m;i++){
            if(2*i>n){
                break;
            }
            __int128 a=n-2*i;//A
            __int128 res1=1;
            __int128 res2=1;
            for(__int128 j=(a+i);j>=(a+1);j--){
                res1=(__int128)(res1*j);
            } 
            for(__int128 j=1;j<=i;j++){
                res2=(__int128)(res2*j);
            } 
            ans+=(__int128)(res1/res2);
        }
        out(ans);
        printf("\n");
    }
}

 

 

组合数学+__int128

标签:clip   ==   阶乘   使用   href   getchar   ++   -o   iostream   

原文地址:https://www.cnblogs.com/lipu123/p/14125315.html

版权声明:完美者 发表于 2020-12-17 12:57:14。
转载请注明:组合数学+__int128 | 完美导航

暂无评论

暂无评论...