2025-05-14：统计能获胜的出招序列数用go语言，Alice 和 Bob 玩一

摘要：2025-05-14：统计能获胜的出招序列数。用go语言，Alice 和 Bob 玩一个回合制幻想战斗游戏，游戏共进行 n 轮。每轮双方同时召唤一种魔法生物，三种生物分别是火龙（F）、水蛇（W）和地精（E）。

2025-05-14：统计能获胜的出招序列数。用go语言，Alice 和 Bob 玩一个回合制幻想战斗游戏，游戏共进行 n 轮。每轮双方同时召唤一种魔法生物，三种生物分别是火龙（F）、水蛇（W）和地精（E）。

得分规则如下：

• 火龙击败地精，召唤火龙的一方得1分。• 水蛇击败火龙，召唤水蛇的一方得1分。• 地精击败水蛇，召唤地精的一方得1分。• 如果双方召唤了相同的生物，则无分。

现在已知 Alice 每一轮召唤的生物序列 s（长度为 n，字符取自 {F, W, E}），但 Bob 的出招序列未知，只知道 Bob 不会连续两次召唤同样的生物。

问题是：满足 Bob 严格得分超过 Alice 的情况下，有多少种不同的 Bob 出招序列？由于结果可能非常大，需要对 1000000007 取模返回。

s[i] 是 'F'、'W' 或 'E' 中的一个。

输入： s = "FWEFW"。

输出： 18。

解释：

Bob 可以通过以下出招序列战胜：Alice："FWFWF"、"FWFWE"、"FWEFE"、"FWEWE"、"FEFWF"、"FEFWE"、"FEFEW"、"FEWFE"、"WFEFE"、"WFEWE"、"WEFWF"、"WEFWE"、"WEFEF"、"WEFEW"、"WEWFW"、"WEWFE"、"EWFWE" 或 "EWEWE"。

题目来自leetcode3320。

使用动态规划来解决这个问题。定义状态 f[i][j][pre]：

• i：已经处理了前 i 轮（从0到n）。• j：当前Bob的净得分（Bob得分 - Alice得分），范围可能在 -n 到 n 之间。• pre：Bob在前一轮出招的生物（0: F, 1: W, 2: E），用于确保当前轮不与前一轮相同。

对于每一轮 i 和当前字符 s[i]（Alice的出招）：

1. 遍历所有可能的净得分 j（从 -i 到 i）。2. 遍历Bob前一轮的出招 pre（0, 1, 2）。3. 对于当前轮，Bob可以选择不与 pre 相同的生物 cur（0, 1, 2且 cur != pre）。4. 计算当前轮的得分贡献：• Bob出 cur，Alice出 mp[s[i]]（将字符映射为数字）。• 计算 score = (cur - mp[s[i]] + 3) % 3，根据得分规则调整：• 如果 score == 2，表示Alice得分，score = -1。• 如果 score == 1，表示Bob得分，score = 1。• 如果 score == 0，表示平局，score = 0。5. 更新净得分 j + score，并将状态转移到 f[i+1][j + score][cur]。

最终答案是 f[n][k][*] 中 k > 0 的所有可能状态的和（即净得分严格大于0的情况）。

package mainimport ( "fmt")func countWinningSequences(s string)int { const mod = 1_000_000_007 mp := [...]int{'F': 0, 'W': 1, 'E': 2} n := len(s) f := make([3]int, n+1) for i := range f { f[i] = make([3]int, n*2+1) } for j := n + 1; j i+1 { f[i+1][j+n][pre] = pow2 continue } res := 0 for cur := 0; cur

Python完整代码如下：

# -*-coding:utf-8-*-defcountWinningSequences(s: str) -> int:mod = 10**9 + 7mp = {'F': 0, 'W': 1, 'E': 2}n = len(s)# f[i][j][pre]: 表示第 i 轮，当前得分差为 j - n（Bob得分- Alice得分），# Bob上一轮召唤的生物是 pre (0:F,1:W,2:E) 的方案数f = [[[0]*3for _ inrange(n*2+1)] for __ inrange(n+1)]# 初始化，得分差大于 n 时方案数为 1for j inrange(n+1, n*2+1):for pre inrange(3):f[0][j][pre] = 1pow2 = 1# 用于快速赋值for i, c inenumerate(s):pow2 = pow2 * 2 % modfor j inrange(-i, n - i):for pre inrange(3):if j > i + 1:f[i+1][j+n][pre] = pow2continueres = 0for cur inrange(3):if i == n - 1or cur != pre:score = (cur - mp[c] + 3) % 3if score == 2:score = -1res += f[i][j + score + n][cur]f[i+1][j+n][pre] = res % modreturn f[n][n][0]if __name__ == "__main__":s = "FWEFW"result = countWinningSequences(s)print(result)