这是一篇发表于 2022年4月1日 的博文，作者将其精简了无聊的 CRUD 部分，保留了对核心机制的探索部分，包括： 明日方舟的公招词条组合优化，明日方舟的抽卡模拟实现，明日方舟的抽卡概率探索。

明日方舟的公招词条组合优化

模拟公招时，以提供五个词条为例，需要将五个词条的所有一词条、二词条、三词条组合都列出，并逐一在公招规则中进行查询，现在需要计算需要查询的词条组合

最简单的办法自然是暴力，获取 $n$ 词条组合这个问题可等价于对一个集合

进行 $n-1$ 次笛卡尔积，将所有结果排序后去重，得到的结果即为所求结果

但是，这个方法效率奇差，不算排序和去重，光是笛卡尔积就需要计算 $5 + 5 \times 5 + 5 \times 5 \times 5 =155$ 次，而此问题的目标输出规模为 $C_5^1 + C_5^2 + C_5^3 = 25$，显然过于离谱

然后自然而然想到了对集合 $A$ 进行全排列，然后进行排序去重，不算排序和去重的话，递归进行全排列的运算次数为 $A_5^1 + A_5^2 + A_5^3 = 85$ 次，此时已经优化了很多了，但还是太离谱了

最后就想到了少有提起的全组合，全组合天然的优势是不用去重和排序，并且全组合的运算次数为 $2^5 = 32$ 次，已经和目标的输出规模很接近了，故采用全组合来实现此需求

对于全组合，我们只需要开辟一个 bool 数组，长度与集合 的元素个数相同即可，按位对应，若元素数量不多，直接使用一个 int 类型的整数类型即可。其 true/false 即为集合对应元素是否出现在结果中，遍历完数组的每一个状态，全组合也就求完了。

这个优化的实现如下，以 golang 作为实现语言：

func combination(tags []string) (result [][]string) {
    length := len(tags)
    upperBound := 1<<length
    result = make([][]string, upperBound-1)

    for i := 1; i < upperBound; i++ {
        temp := ""
        for j := 0; j < length; j++ {
            if i>>j == 0 {
                break
            } else {
                if (i>>j)^1 == 1 {
                    temp += tags[j] + ","
                }
            }
        }
        result[i-1] = strings.Split(strings.TrimRight(temp, ","), ",")
    }

    return result
}

明日方舟的抽卡模拟实现

由于完全随机较容易出现极端值，我们可以调一个正态的图形出来

尝试过调模型了，事实证明这个活适合专业人士去干，想用喜闻乐见的十倍开根号进行修正，结果调出了极其奇怪的图像🤦，有兴趣的同学可以自己去试试

简单测试了一下 rand 库的随机数函数的生成效率，生成 $1024$ 组，每组 $2^20$ 个随机数，所用时间为十二秒 (测试平台为 Apple M1)，对于抽卡而言性能 我猜 够了

gacha 的实现如下，精确度为小数点后六位，以 golang 作为实现语言：

func gacha(alreadyGacha, count, fourStar, fiveStar, sixStar, sixStarCorrection int) (result []int) {
    result = make([]int, count)
    correctionSixStar := sixStar
    
    for i, _ := range result {
        if alreadyGacha >= 50 {
            correctionSixStar += sixStarCorrection
        }

        prop := rand.Int() % 1000000
        alreadyGacha += 1
        if prop < fourStar {
            result[i] = 3
            continue
        }
        switch {
        case prop > correctionSixStar:
            result[i] = 6
            alreadyGacha = 0
            correctionSixStar = sixStar
        case prop > fiveStar:
            result[i] = 5
        default:
            result[i] = 4
        }
    }

    return result
}

明日方舟的抽卡概率探索

我们知道随机事件 $A$ 发生的概率为 $P$，即抽卡出货的概率为 $2\%$，那么 $A$ 的对立事件 $\overline{A}$ 即抽卡不出货的概率为 $1-2\% = 98\%$，则连续两次抽卡不出货的概率为 $P(\overline{A}) \times P(\overline{A}) = 98\% \times 98\%$，以此类推，五十抽以内，前 $n$ 次抽卡都不出货的概率为 $P(n) = (0.98)^{n}$

但是当抽卡次数达到 $50$ 抽以上时，将会触发概率补正，即增加 $2\%$ 的额外概率，五十抽以后，再抽一发还不出货的概率为 $P(n) \times P(n)'$，其中 $P(n)$ 为该抽前不出货的概率，$P'(n) = 2% + (n-50) \times 2%$，$n$ 为已经抽卡次数

那么连续抽 $n$ 次都不出货的概率 $P(n)$ 表达式如下：

那么，连续抽 $n$ 次至少出一张六星的概率 $P'(n) = 1-P(n)$，我们假定当至少出一张六星的概率大于 $99.9\%$ 时，下一抽必出货

顶着 float64 溢出的边缘计算，得到结果：当抽卡 $74$ 次仍没出货时，下一抽的出货的概率至少为 $99.9\%$ 。好想去问候鹰角为什么我四五次到了 70-77 抽才出货

至于那个网上流传已久的期望 抽是怎么来的，可以参考这篇文章 ^{[^知乎-从明日方舟抽卡机制开始的些微探索]}