ARST打卡第345周

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int numberOfWays(string corridor) {
        const int MOD = 1e9 + 7;
        vector<int> sIdx;
        int n = corridor.size();
        // 记录所有凳子的索引
        for (int i = 0; i < n; ++i) {
            if (corridor[i] == 'S') sIdx.push_back(i);
        }
        int S = sIdx.size();
        // 如果S不是偶数且不够2则无解
        if (S == 0 || S % 2 != 0) return 0;
        if (S == 2) return 1; // 只有一段被锁死，只有一种隔法
        long long ans = 1;
        // 每对之间锁死，统计所有段的植物，计算（段长+1）的积
        for (int i = 1; i + 1 < S; i += 2) {
            int l = sIdx[i];
            int r = sIdx[i + 1];
            ans = ans * (r - l) % MOD;
        }
        return ans;
    }
};