../ Competitive Programming

-rw-r--r--aguang1.5 KiB2024-05-262 min read

Leet Code Daily 2024-05-26

Leet Code Daily 2024-05-26 - Student Attendance Record II

Description

Solution

It's just math..

Let's say $F(n)$ is the number of possible student attendance records of which:

The last record is P.
It contains no record A.
It has no more than two consecutive L records.

F(n) = \begin{cases} 1 & n = 0 \\ 2^{n - 1} & 1 \leq n \leq 3 \\ F(n - 1) + F(n - 2) + F(n - 3) & n > 3 \\ \end{cases}

Let's say $G(n)$ is the number of possible student attendance records of which:

It contains no record A.
It has no more than two consecutive L records.

G(n) = \sum_{i = max(n - 2, 0)}^{n} F(n)

Now considering at most one record A, the final answer would be:

G(n) + \sum_{i = 0}^{n - 1} G(i) \times G(n - i - 1)

Code

c++

constexpr long long kMod = 1E9 + 7;

class Solution {
public:
    int checkRecord(int n) {
        vector<long long> f = {1, 1, 2, 4}, g;
        for (int i = 4; i <= n; i++) {
            f.push_back((f[i - 1] + f[i - 2] + f[i - 3]) % kMod);
        }
        for (int i = 0; i <= n; i++) {
            g.push_back(accumulate(next(f.begin(), max(i - 2, 0)),
                                   next(f.begin(), i + 1), 0LL) %
                        kMod);
        }
        long long ans = g[n];
        for (int i = 0; i <= n - 1; i++) {
            ans = (ans + g[i] * g[n - i - 1]) % kMod;
        }
        return ans;
    }
};

press any key / click to skip