牛客 挑选方案问题（排列组合）

文章目录

• • 1. 题目
  • 2. 解题

1. 题目

链接：https://ac.nowcoder.com/acm/contest/10323/B 来源：牛客网

自助餐厅里有5个盘子，里面装的都是面包。 第1个盘子里有无限个面包； 第2个盘子里只有1个面包； 第3个盘子里只有4个面包； 第4个盘子里也有无限个面包，但必须两个两个地拿； 第5个盘子里也有无限个面包，但必须5个5个地拿； 给定正整数n，求有多少种正好拿出n个面包的方案。

方案a和方案b不同，当且仅当方案a存在从某个盘子里拿出面包的数量与方案b中对应盘子拿出的数量不同。

示例1
输入
1
返回值
3
说明
有3种方案：
在第一个盘子拿一个。
在第二个盘子拿一个。
在第三个盘子拿一个。

示例2
输入
2
返回值
6
说明
有6种方案：
在第一个盘子拿2个。
在第一个盘子拿1个，第二个盘子拿1个。
在第一个盘子拿1个，第三个盘子拿1个。
在第二个盘子拿1个，第三个盘子拿1个。
在第三个盘子拿2个。
在第四个盘子拿2个。
（请注意由于第四个盘子里只能两个两个拿，所以必须拿偶数个）

备注:
n<=10^9
数据仅包含一个正整数n
输出一个正整数表示答案。

2. 解题

• 设 1,4,5号盘子 每个盘子拿的次数为 x,y,z；2,3号盘子拿出来的个数 a,b
• 则 x + 2 ∗ y + 5 ∗ z + a + b = n , a n d a < = 1 , b < = 4 x+2*y+5*z+a+b=n, and \quad a<=1 ,\quad b<=4 x+2∗y+5∗z+a+b=n,anda<=1,b<=4
• 将式子变形为 ( x ) + ( 2 y + a ) + ( 5 z + b ) = n (x)+(2y+a)+(5z+b)=n (x)+(2y+a)+(5z+b)=n，每个括号里面都可以表示任意数字，且一旦括号的值给定了，两个变量的值是唯一的
• 3个任意数字相加等于 n，把 n 个数分成3份
• 第一个数取0，还剩余 n 个 数2个人分，有 n+1 种方案
• 第一个数取1，还剩余 n-1 个 数2个人分，有 n 种方案
• …
• 第一个数取n，还剩余 0 个 数2个人分，有 1 种方案

总方案数为 1 + 2 + . . . + ( n + 1 ) = ( n + 2 ) ∗ ( n + 1 ) / 2 = C n + 2 2 1+2+...+(n+1) = (n+2)*(n+1)/2=C_{n+2}^2 1+2+...+(n+1)=(n+2)∗(n+1)/2=Cn+22​

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 
     * @return long长整型
     */
    long long wwork(int n) {
        // write code here
        return 1LL*(n+2)*(n+1)/2;
    }
};