阿里笔试9.4

阿里9.4笔试太难了吧，自闭了，太久没做题，第一题想动态规划想多了，第二题树和森林看完弃
第一题
题目本质：将a b c d 填入n×n格子的组合数
保证 a+b+c+d = n×n
数据范围 0<=n<=10
输入 ：n a b c d
输出 ：组合数ans
注意：对998244353取模

组合数公式 ：C(n,m) = n!/(m!(n-m)!)
解题思路：
C(n×n,a)×C(n×n-a,b)×C(n×n-a-b,c)×C(n×n-a-b-c,d）
C++用乘法逆元求组合数可过100%;
java用记忆化回溯AC的：

作者：AtlanTa.
链接：https://www.nowcoder.com/discuss/498406?type=post&order=time&pos=&page=2&channel=1009&source_id=search_post
来源：牛客网

public class Main2 {
    static long[][][][][] memo;
    public static long dfs(int[] choice, int start, int n) {
        if (memo[choice[0]][choice[1]][choice[2]][choice[3]][start] != 0) {
            return memo[choice[0]][choice[1]][choice[2]][choice[3]][start];
        }
        if (start == n) {
            return 1;
        } else {
            long temp = 0;
            for (int i = 0; i < 4; i++) {
                if (choice[i] > 0) {
                    choice[i]--;
                    temp += dfs(choice, start + 1, n);
                    choice[i]++;
                }
            }
            temp %= 998244353;
            memo[choice[0]][choice[1]][choice[2]][choice[3]][start] = temp;
            return temp;
        }
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int up = in.nextInt();
        int down = in.nextInt();
        int left = in.nextInt();
        int right = in.nextInt();
        int[] choice = new int[]{up, down, left, right};
        memo = new long[up + 1][down + 1][left + 1][right + 1][n * n + 1];
        System.out.print(dfs(choice, 0, n * n));
    }
}

python的阶乘函数可用factorial 计算（N*N）! /(a!b!c!d!)
贴个C(n×n,a)×C(n×n-a,b)×C(n×n-a-b,c)×C(n×n-a-b-c,d）代码

作者：ming0527
链接：https://www.nowcoder.com/discuss/498406?type=post&order=time&pos=&page=2&channel=1009&source_id=search_post
来源：牛客网

第一题python代码：
def jiecheng(n): #阶乘
    ans = 1
    while n:
        ans *= n
        n = n-1
    return ans

def C(m,n):   #全排列
    up = jiecheng(m)
    down = jiecheng(n)*jiecheng(m-n)
    return up/down

while True:
    try: 
        N,a,b,c,d = list(map(int,raw_input().split()))
        arr = [a,b,c,d]
#        arr.remove(0)
        N = N**2

        ans = 1
        for i in arr:
            ans *= C(N,i)
            N = N-i
        print(int(ans%998244353))
    except:
        break

第二题
一个保存了各条边的树，删除某个叶子节点，并同时删除从根节点到该叶子节点路径上的所有节点，问剩下的树的个数的最大值。
输入: n
n行v w表示节点的边
输出：剩下的树的个数的最大值
坑点：可多次删除
求大佬解题思路