官解：Terrorists

· · 题解

前置知识

算法 1

考虑暴力。对每一天枚举点对，朴素实现 DP 的复杂度为 O(N \cdot m^2)。

期望得分 20pts。

算法 2

不难想到记录能够转移的点对来优化转移。

由于数据随机，转移方案数应该是蛮少的。

可能有点卡常，但确实能过。

期望得分 50pts。

算法 3

按照算法 2 的想法，既然转移点对都是固定的，那么这个 DP 就是固定的线性递推关系。

考虑矩阵加速，时间复杂度为 O(m^3\log N)。

期望得分 \text{100 pts}。

code

避免有人说算法 2 过不了，我粘个码。

int run[105][105];
int tot[105];
inline void Add(int &a, int b){
    a += b;
    (a >= MOD ? a -= MOD : a);
}
int f[105], lst[105];
int main() {
    for (int j = 0; j < m; ++ j) {
            for (int k = 0; k < m; ++ k) {
                if (persons[j].t <= persons[k].t && persons[j].c >= persons[k].c) {
                    if (persons[j].g == 'g' || persons[j].l <= persons[k].l) {
                        run[j][++ tot[j]] = k;
                    }
                }
            }
        }
    while (N --) {
        memcpy(lst, f, sizeof(int) * m);
        memset(f, 0, sizeof(int) * m);
        for (int j = 0; j < m; ++ j) {
            for (int p = tot[j]; p;){
                Add(f[j], lst[run[j][p --]]);
            }
        }
    }
    for (int i = 0; i < m; i++)
        Add(ans, f[i]);
}