首页 > 试题广场 >

工作方案

[编程题]工作方案
  • 热度指数:99 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 150M,其他语言300M
  • 算法知识视频讲解
牛牛手中有s份工作需要完成,牛牛准备将工作分给三位员工。考虑到三位员工还有其他工作需要做,牛牛规定他们每人必须要参与的工作数量分别是a,b,c。
牛牛需要制定详细的工作方案,需要满足每份工作至少有一个人做,同一份工作可以由两个或者三个人共同参与。牛牛一下意识到可能的工作方案很多,牛牛需要你帮他计算一下一共有多少种不同的工作方案(对于两种方案,如果某份工作分配的人或者人数不一样就考虑为不一样的工作方案)。

对于输入样例,s = 3, a = 3, b = 1, c = 1
a要参与所有三份工作,b和c各自有三种选择,所以不同的工作方案是3 * 3 * 1= 9
如果s = 3, a = 1, b = 1, c = 1
相当于对三个员工做全排列,所以不同的工作方案是3 * 2 * 1 = 6

输入描述:
输入包括一行,一行包括4个正整数s,a,b,c(1 ≤ s ≤ 50, 1 ≤ a, b, c ≤ s),分别表示需要完成的工作份数,每个员工必须要参与的工作数量。


输出描述:
输出一个正整数,表示不同的方案种数,答案可能很大,输出答案对1000000007取模。
示例1

输入

3 3 1 1

输出

9

先选a
剩余 s-a ,b 和 c 完成剩余的空位填充
然后分情况:

0个b,s-a个c
1个b,s-a-1个c
...
s-a个b,0个c

每次计算b填充i个,剩余的b-i填充到a,c填充s-a-i个,剩余的c-(s - a - i) 填充到 a + i
然后排列组合所有情况,并处理边界情况即可
import java.util.Scanner;
public class Main {
    private static int s;
    private static int a, b, c;
    private static final int MOD = 1000000007;
    public static void main(String[] args){
        int loop = 1;
        Scanner scanner = new Scanner(System.in);
        //loop = scanner.nextInt();
        for (; loop-- > 0;) {
            s = scanner.nextInt();
            a = scanner.nextInt();
            b = scanner.nextInt();
            c = scanner.nextInt();
            solve();
        }
        scanner.close();
    }
    private static void solve() {
        long cnt = 0;
        int left = s - a; // a put
        for (int i = Math.max(Math.max(0, left - c), b - a); i <= Math.min(b, left); i++) {
            // b get i in left, c get left - i in left
            cnt += ((C(i, left)* C(b - i, a) % MOD) * C(c - left + i, a + i)) % MOD;
        }
        cnt *= C(a, s);
        System.out.println(cnt % MOD);
    }
    // C m in n
    private static long C(int m, int n) {
        double d = 1;
        for (int i = 0, len = m; i < len; i++) {
            d = d * n-- / m--;
        }
        return Math.round(d) % MOD;
    }
}
编辑于 2018-07-21 09:00:25 回复(2)