地精部落

[Ameiyo ]

求一个序列满足，每个点两边与其大小关系相同

考虑一个 $ Dp $ ， $ f[i][j][0/1] $ 表示比上一个大的数有 $ i $ 个，比他小的数有 $ j $ 个，并且上上个和上一个的关系是 $ 0 $

那么 $ 0 $ 只能转移到 $ 1 $ ， $ 1 $ 只能转移到 $ 0 $

每次枚举相对距离 $ x $ ，以 $ 0 $ 为例

[f[i][j][0] -> f[i - x][j + x - 1][1] (1 <= x <= i) ]

这不像是一个可以优化的东西。。。

换一下， $ f[i][j][0/1] $ 表示放了 $ i $ 个，比第 $ i $ 个数大的数有 $ j $ 个，其他同上

同理

[f[i][j][0] -> f[i + 1][j - x][1] (1 <= x <= j) ]

在计算 1 的情况时，先算出比第 $ i $ 个小的数量 $ d = n - i - j $

新的比他小的数量就是 $ d - x (1 <= x <= d) $

那么新的比他大的数量就是

[n - (i + 1) - (d - x) = n - (i + 1) - (n - i - j - x) = j + x - 1 ]

[f[i][j][1] -> f[i][j + x - 1][0] (1 <= x <= n - i - j) ]

所以

[f[i][j][1] = sum f[i - 1][j + x][0] ]

[f[i][j][0] = sum f[i - 1][j - x + 1][1] ]

复杂度 $ O(n ^ 2) $

int n, Mod, f[N][N][2];

int main() {
    n = read<int>(), Mod = read<int>();
    rep (j, 0, n - 1) f[1][j][0] = f[1][j][1] = 1;
    rep (i, 2, n) {
        int sum = 0;
        dep (j, n - i + 1, 0) {
            f[i][j][0] = sum;
            ((sum += f[i - 1][j][1]) >= Mod && (sum -= Mod));
        }
        sum = 0;
        rep (j, 0, n - i + 1) {
            ((sum += f[i - 1][j][0]) >= Mod && (sum -= Mod));
            f[i][j][1] = sum;
        }
    }

    printf("%d
", (f[n][0][0] + f[n][0][1]) % Mod);
    return 0;
}

[in 2019.10.31 ]