1 条题解

  • 1
    @ 2022-2-22 19:12:18

    在我的个人博客中阅读

    Greg and Caves

    题意

    问满足下列条件的 n×mn \times m 的 01 矩阵 aa 的数量:

    1. [l, r](1lrn)\exists [l,~r] (1 \le l \le r \le n),满足 i[l, r], jai,j=2\forall i \in [l,~r],~\sum_j a_{i,j} =2i[l, r], jai,j=0\forall i \notin [l,~r],~\sum_j a_{i,j}=0
    2. [l, r][l,~r] 中的每一行的第一个值为 11 的位置的下标为 xix_i,第二个值为 11 的位置的下标为 yiy_i,则:t[l, r]\exists t \in [l,~r],满足 i[l, t1], xixi+1, yiyi+1\forall i \in [l,~t-1],~x_i \ge x_{i+1},~y_i \le y_{i+1}i[t, r1], xixi+1, yiyi+1\forall i \in [t,~r-1],~x_i \le x_{i+1},~y_i \ge y_{i+1}

    分析

    考虑使用 DP 解决本题。

    f[i][j]f[i][j] 表示考虑洞的前 ii 行(该 ii 行都在洞的中间位置 tt 的上方)且第 ii 行的 yixi+1=jy_i-x_i+1=j 时该洞的构造方案(不考虑洞在矩阵中的摆放位置)。

    考虑枚举第 i1i-1 行的长度以及与第 ii 行的相对位置,得出转移方程:

    f[i][j]=t=0jf[i1][t]×(jt+1)f[i][j]=\sum_{t=0}^{j}f[i-1][t] \times (j-t+1)

    尝试使用该数据描述最终答案 AnsAns,考虑枚举中间位置 tt 的行编号以及该行 yixi+1y_i-x_i+1 的大小。同时由于可能存在构造洞的方案满足第 tt 行与相邻的几行的形态完全相同,为了防止算重,考虑令 tt 为洞的最大的满足 yixi+1y_i-x_i+1 最大的行数,同时枚举 t+1t+1 行的长度(小于 tt 行长度),算出最终答案:

    Ans=i=1na=0m2(ma1)×(l=1if[il+1][a])×(1+b=0a1(r=i+1nf[ri][b])×(ab+1))=i=1na=0m2(ma1)×(t=1if[t][a])×(1+b=0a1(t=1nif[t][b])×(ab+1))\begin{aligned} Ans&=\sum_{i=1}^{n} \sum_{a=0}^{m-2} (m-a-1) \times \big( \sum_{l=1}^{i} f[i-l+1][a] \big) \times (1 + \sum_{b=0}^{a-1} \big( \sum_{r=i+1}^{n} f[r-i][b] \big) \times (a - b + 1))\\\\ &=\sum_{i=1}^{n} \sum_{a=0}^{m-2} (m-a-1) \times \big( \sum_{t=1}^{i} f[t][a] \big) \times (1 + \sum_{b=0}^{a-1} \big( \sum_{t=1}^{n-i} f[t][b] \big) \times (a - b + 1)) \end{aligned}

    g[i][j]=k=1if[k][j]g[i][j] = \sum_{k=1}^{i} f[k][j]

    Ans=i=1na=0m2(ma1)×g[i][a]×(1+b=0a1g[ni][b]×(ab+1))Ans=\sum_{i=1}^{n} \sum_{a=0}^{m-2} (m-a-1) \times g[i][a] \times (1 + \sum_{b=0}^{a-1} g[n-i][b] \times (a-b+1))

    h[i][j]=k=0j1g[i][k]×(jk+1)h[i][j]=\sum_{k=0}^{j-1} g[i][k] \times (j-k+1)

    Ans=i=1na=0m2(ma1)×g[i][a]×(1+h[ni][a])Ans=\sum_{i=1}^{n} \sum_{a=0}^{m-2} (m-a-1) \times g[i][a] \times (1 + h[n-i][a])

    处理 f[i][j]f[i][j] 前缀和优化到 O(nm)O(nm),处理 g[i][j]g[i][j] O(nm)O(nm),处理 h[i][j]h[i][j] 前缀和优化到 O(nm)O(nm),计算答案 AnsAns O(nm)O(nm)

    总时间复杂度 O(nm)O(nm)

    代码

    View On GitHub

    Code
    /**
     * @author Macesuted (macesuted@outlook.com)
     * @copyright Copyright (c) 2021
     * @brief
     *      My solution: https://macesuted.moe/article/cf295d
     */
    
    #include <bits/stdc++.h>
    using namespace std;
    
    namespace io {
    #define SIZE (1 << 20)
    char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55];
    int f, qr;
    inline void flush(void) { return fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void(); }
    inline char getch(void) { return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++); }
    inline void putch(char x) {
        *oS++ = x;
        if (oS == oT) flush();
        return;
    }
    string getstr(void) {
        string s = "";
        char c = getch();
        while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = getch();
        while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)) s.push_back(c), c = getch();
        return s;
    }
    void putstr(string str, int begin = 0, int end = -1) {
        if (end == -1) end = str.size();
        for (register int i = begin; i < end; i++) putch(str[i]);
        return;
    }
    template <typename T>
    inline T read() {
        register T x = 0;
        for (f = 1, c = getch(); c < '0' || c > '9'; c = getch())
            if (c == '-') f = -1;
        for (x = 0; c <= '9' && c >= '0'; c = getch()) x = x * 10 + (c & 15);
        return x * f;
    }
    template <typename T>
    inline void write(const T& t) {
        register T x = t;
        if (!x) putch('0');
        if (x < 0) putch('-'), x = -x;
        while (x) qu[++qr] = x % 10 + '0', x /= 10;
        while (qr) putch(qu[qr--]);
        return;
    }
    struct Flusher_ {
        ~Flusher_() { flush(); }
    } io_flusher_;
    }  // namespace io
    using io::getch;
    using io::getstr;
    using io::putch;
    using io::putstr;
    using io::read;
    using io::write;
    
    #define maxn 2005
    #define mod 1000000007
    
    long long f[maxn][maxn], g[maxn][maxn], h[maxn][maxn], cac[maxn][maxn];
    
    int main() {
        int n = read<int>(), m = read<int>();
        for (register int i = 0; i <= m - 2; i++) f[1][i] = 1;
        for (register int i = 2; i <= n; i++) {
            f[i][0] = cac[i][0] = f[i - 1][0];
            for (register int j = 1; j <= m - 2; j++)
                cac[i][j] = (cac[i][j - 1] + f[i - 1][j]) % mod, f[i][j] = (f[i][j - 1] + cac[i][j]) % mod;
        }
        for (register int i = 1; i <= n; i++)
            for (register int j = 0; j <= m - 2; j++)
                g[i][j] = (g[i - 1][j] + f[i][j]) % mod;
        memset(cac, 0, sizeof(cac));
        for (register int i = 1; i < n; i++)
            for (register int j = 1; j <= m - 2; j++)
                cac[i][j] = (cac[i][j - 1] + g[i][j - 1]) % mod, h[i][j] = (h[i][j - 1] + cac[i][j] + g[i][j - 1]) % mod;
        long long answer = 0;
        for (register int i = 1; i <= n; i++)
            for (register int j = 0; j <= m - 2; j++)
                answer = (answer + (m - j - 1) * g[i][j] % mod * (1 + h[n - i][j])) % mod;
        write(answer), putch('\n');
        return 0;
    }
    
    • 1

    信息

    ID
    5762
    时间
    2000ms
    内存
    256MiB
    难度
    9
    标签
    递交数
    1
    已通过
    1
    上传者