2022-05-29：为了不断提高用户使用的体验，开发团队正在对产品进行全方位的开发和优化。

原创

福大大架构师每日一题

发布于 2022-05-29 12:03:10

1571

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2022-05-29：为了不断提高用户使用的体验，开发团队正在对产品进行全方位的开发和优化。

已知开发团队共有若干名成员，skillsi 表示第 i 名开发人员掌握技能列表。

如果两名成员各自拥有至少一门对方未拥有的技能，则这两名成员可以「合作开发」。

请返回当前有多少对开发成员满足「合作开发」的条件。

由于答案可能很大，请你返回答案对 10^9 + 7 取余的结果。

来自银联编程比赛。

答案2022-05-29：

总数-不合法的=合法的。

位运算。

代码用rust编写。代码如下：

use std::collections::HashMap;
fn main() {
    let mut arr: Vec<Vec<isize>> = vec![vec![1, 2, 3], vec![3], vec![2, 4]];
    let ans = coop_develop(&mut arr);
    println!("ans = {}", ans);
}

fn coop_develop(skills: &mut Vec<Vec<isize>>) -> isize {
    const MOD: isize = 1000000007;
    let n = skills.len() as isize;
    // key : 子集
    // value : 个数
    let mut no_full_sets_nums: HashMap<isize, isize> = HashMap::new();
    for people in skills.iter_mut() {
        fill_no_full_map(people, 0, 0, true, &mut no_full_sets_nums);
    }
    let mut cnts_nums: HashMap<isize, isize> = HashMap::new();
    let mut minus: isize = 0;
    for people in skills.iter_mut() {
        let mut status: isize = 0;
        for skill in people {
            status = (status << 10) | *skill;
        }
        minus += if no_full_sets_nums.contains_key(&status) {
            *no_full_sets_nums.get(&status).unwrap()
        } else {
            0
        };
        minus += if cnts_nums.contains_key(&status) {
            *cnts_nums.get(&status).unwrap()
        } else {
            0
        };
        cnts_nums.insert(
            status,
            if cnts_nums.contains_key(&status) {
                *cnts_nums.get(&status).unwrap()
            } else {
                0
            } + 1,
        );
    }
    let ans = n * (n - 1) / 2;
    return (ans - minus) % MOD;
}

fn fill_no_full_map(
    people: &mut Vec<isize>,
    i: isize,
    status: isize,
    full: bool,
    no_full_sets_nums: &mut HashMap<isize, isize>,
) {
    if i == people.len() as isize {
        if !full {
            no_full_sets_nums.insert(
                status,
                if no_full_sets_nums.contains_key(&status) {
                    *no_full_sets_nums.get(&status).unwrap()
                } else {
                    0
                } + 1,
            );
        }
    } else {
        fill_no_full_map(people, i + 1, status, false, no_full_sets_nums);
        fill_no_full_map(
            people,
            i + 1,
            (status << 10) | people[i as usize],
            full,
            no_full_sets_nums,
        );
    }
}