lc552 学生出勤记录2

有n天，每天出勤可以是缺勤，迟到或正常，要求总缺勤天数少于两天，且不存在连续3天及以上的迟到，问有多少种可行的情况？结果对1e9+7取模。
1<=n<=1e5

记数类dp问题，用刷表法好写点，即假设当前为第i天，已缺勤j天，已连续迟到k天，方案数为dp[i][j][k]，再分别枚举接下的一天选择什么，来更新第i+1天的结果。当然也可以用记忆化dfs来写，另外还可以用矩阵快速幂加速到O(logn)。

template<int MOD>
struct MInt {
    int x;
    int norm(int u) const {u%=MOD; if(u<0) u+=MOD; return u;}
    MInt(int v=0):x(norm(v)) {}
    int val() const {return x;}
    MInt operator-() const {return MInt(norm(MOD-x));}
    MInt inv() const {assert(x!=0); return power(MOD-2);}
    MInt &operator*=(const MInt &o) {x=norm(x*o.x); return *this;}
    MInt &operator+=(const MInt &o) {x=norm(x+o.x); return *this;}
    MInt &operator-=(const MInt &o) {x=norm(x-o.x); return *this;}
    MInt &operator/=(const MInt &o) {*this *= o.inv(); return *this;}
    friend MInt operator*(const MInt &a, const MInt &b) {MInt ans=a; ans*=b; return ans;}
    friend MInt operator+(const MInt &a, const MInt &b) {MInt ans=a; ans+=b; return ans;}
    friend MInt operator-(const MInt &a, const MInt &b) {MInt ans=a; ans-=b; return ans;}
    friend MInt operator/(const MInt &a, const MInt &b) {MInt ans=a; ans/=b; return ans;}
    friend std::istream &operator>>(std::istream &is, MInt &a) {int u; is>>u; a=MInt(u); return is;}
    friend std::ostream &operator<<(std::ostream &os, const MInt &a) {os<<a.val(); return os;}
    MInt power(int b) const {int r=1, t=x; while(b){if(b&1) r=r*t%MOD; t=t*t%MOD; b/=2;} return MInt(r);}
};
using mint = MInt<1000000007>;

const int N = 100005;
mint dp[N][2][3];
class Solution {
public:
    int checkRecord(int n) {
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 3; k++) {
                    dp[i][j][k] = 0;
                }
            }
        }
        dp[0][0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 3; k++) {
                    dp[i+1][j][0] += dp[i][j][k];
                    if (k < 2) dp[i+1][j][k+1] += dp[i][j][k];
                    if (j < 1) dp[i+1][j+1][0] += dp[i][j][k];
                }
            }
        }
        mint ans = 0;
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 3; k++) {
                ans += dp[n][j][k];
            }
        }
        return ans.val();
    }
};