Alice and Bob are playing a fantasy battle game consisting of n rounds where they summon one of three magical creatures each round: a Fire Dragon, a Water Serpent, or an Earth Golem. In each round, players simultaneously summon their creature and are awarded points as follows:
If one player summons a Fire Dragon and the other summons an Earth Golem, the player who summoned the Fire Dragon is awarded a point.
If one player summons a Water Serpent and the other summons a Fire Dragon, the player who summoned the Water Serpent is awarded a point.
If one player summons an Earth Golem and the other summons a Water Serpent, the player who summoned the Earth Golem is awarded a point.
If both players summon the same creature, no player is awarded a point.
You are given a string s consisting of n characters 'F', 'W', and
'E', representing the sequence of creatures Alice will summon in each round:
If s[i] == 'F', Alice summons a Fire Dragon.
If s[i] == 'W', Alice summons a Water Serpent.
If s[i] == 'E', Alice summons an Earth Golem.
Bob’s sequence of moves is unknown, but it is guaranteed that Bob will never summon the same creature in two consecutive rounds. Bob beats Alice if the total number of points awarded to Bob after n rounds is strictly greater than the points awarded to Alice.
Return the number of distinct sequences Bob can use to beat Alice.
Since the answer may be very large, return it modulo10^9 + 7.
Input: s ="FFF"Output: 3Explanation:
Bob can beat Alice by making one of the following sequences of moves:`"WFW"`,`"FWF"`, or `"WEW"`. Note that other winning sequences like `"WWE"` or `"EWW"`are invalid since Bob cannot make the same move twice in a row.
Input: s ="FWEFW"Output: 18Explanation:
Bob can beat Alice by making one of the following sequences of moves:`"FWFWF"`,`"FWFWE"`,`"FWEFE"`,`"FWEWE"`,`"FEFWF"`,`"FEFWE"`,`"FEFEW"`,`"FEWFE"`,`"WFEFE"`,`"WFEWE"`,`"WEFWF"`,`"WEFWE"`,`"WEFEF"`,`"WEFEW"`,`"WEWFW"`,`"WEWFE"`,`"EWFWE"`, or `"EWEWE"`.
Bob must never repeat the same creature in consecutive rounds, and his goal is to strictly outscore Alice. We can use dynamic programming to count all valid Bob’s sequences, tracking the current round, the last creature Bob played, and the current score difference (Bob’s points minus Alice’s points). We use state compression to keep the DP feasible.
classSolution {
public:int countWinningSequences(string s) {
constint MOD =1e9+7;
int n = s.size();
vector<int> alice(n);
for (int i =0; i < n; ++i) {
if (s[i] =='F') alice[i] =0;
elseif (s[i] =='W') alice[i] =1;
else alice[i] =2;
}
vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(4, vector<int>(2*n+1, -1)));
function<int(int,int,int)> dfs = [&](int i, int last, int diff) ->int {
if (i == n) return diff >0?1:0;
int&res = dp[i][last][diff+n];
if (res !=-1) return res;
res =0;
for (int b =0; b <3; ++b) {
if (b == last) continue;
int d =0;
if ((b ==0&& alice[i] ==2) || (b ==1&& alice[i] ==0) || (b ==2&& alice[i] ==1)) d =1;
elseif ((alice[i] ==0&& b ==2) || (alice[i] ==1&& b ==0) || (alice[i] ==2&& b ==1)) d =-1;
res = (res + dfs(i+1, b, diff+d)) % MOD;
}
return res;
};
int ans =0;
for (int b =0; b <3; ++b) {
ans = (ans + dfs(0, b, 0)) % MOD;
}
return ans;
}
};
classSolution {
funcountWinningSequences(s: String): Int {
val MOD = 1_000_000_007
val n = s.length
val alice = IntArray(n) { when (s[it]) { 'F'->0; 'W'->1; else->2 } }
val dp = Array(n+1) { Array(4) { IntArray(2*n+1) { -1 } } }
fundfs(i: Int, last: Int, diff: Int): Int {
if (i == n) returnif (diff > 0) 1else0if (dp[i][last][diff+n] != -1) return dp[i][last][diff+n]
var res = 0for (b in0..2) {
if (b == last) continuevar d = 0if ((b ==0&& alice[i] ==2) || (b ==1&& alice[i] ==0) || (b ==2&& alice[i] ==1)) d = 1elseif ((alice[i] ==0&& b ==2) || (alice[i] ==1&& b ==0) || (alice[i] ==2&& b ==1)) d = -1 res = (res + dfs(i+1, b, diff+d)) % MOD
}
dp[i][last][diff+n] = res
return res
}
var ans = 0for (b in0..2) {
ans = (ans + dfs(0, b, 0)) % MOD
}
return ans
}
}
classSolution:
defcountWinningSequences(self, s: str) -> int:
MOD =10**9+7 n = len(s)
alice = [0if c =='F'else1if c =='W'else2for c in s]
from functools import lru_cache
@lru_cache(maxsize=None)
defdfs(i: int, last: int, diff: int) -> int:
if i == n:
return1if diff >0else0 res =0for b in range(3):
if b == last:
continue d =0if (b ==0and alice[i] ==2) or (b ==1and alice[i] ==0) or (b ==2and alice[i] ==1):
d =1elif (alice[i] ==0and b ==2) or (alice[i] ==1and b ==0) or (alice[i] ==2and b ==1):
d =-1 res = (res + dfs(i+1, b, diff+d)) % MOD
return res
ans =0for b in range(3):
ans = (ans + dfs(0, b, 0)) % MOD
return ans