NekoMio's Blog

美しいものが起こることを常に信じている

  1. 1. 题目描述
  2. 2. 输入格式
  3. 3. 输出格式
  4. 4. 样例
    1. 4.1. 样例 1 输入
    2. 4.2. 样例 1 输出
    3. 4.3. 样例 1 解释
    4. 4.4. 样例 2 输入
    5. 4.5. 样例 2 输出
  5. 5. 数据范围与提示
  • 题解
  • 题目描述

    莫斯科吹的寒风 / 仿佛昨日那场梦 / 啊 你还会记得我吗

    1941.12.

    寒冷刺骨的天气、疲惫不堪的军队……包围首都的作战计划陷入了困境。空军或许是拯救战况的最后希望了,元首 Adolf 想道。

    在一个 $n \times m$ 的网格区域中存在一个陆军单位需要补给,区域中的每个格子为空地或障碍物中的一种。航空舰队需要派遣若干运输机前往此区域,每一架运输机可以向两个相邻(有一条公共边)的空地投放物资。为防止不必要的损坏,一个标记为空地的格子至多只能得到一次投放。

    由于天气原因,陆军单位所在的确切位置并不能确定。因此元首想知道,对于每个空地格子,当陆军单位在其中(视作障碍物)时,用若干(可以为 $0$)架运输机向其余空地投放任意数量的物资的不同方案数。两个投放方案不同,当且仅当存在一个格子在一个方案中被投放而另一方案中未被投放,或存在两个被投放的格子,在一个方案中被同一架运输机投放而在另一方案中非然。若仍有疑问,请参考「样例 1 解释」。

    你需要编写程序帮助元首计算这些值对 $10^9+7$ 取模的结果。

    输入格式

    从标准输入读入数据。

    • 第 $1$ 行:两个空格分隔的正整数 $n,m$ —— 网格区域的行数和列数。
    • 接下来 $n$ 行:其中第 $i$ 行包含 $m$ 个空格分隔的整数 $A_{i1},A_{i2},\ldots,A_{im}$ —— 其中 $A_{ij} = 0$ 表示第 $i$ 行第 $j$ 列的格子为空地; $A_{ij} = 1$表示该格为障碍物

    输出格式

    输出到标准输出。

    对于每组数据输出 $n$ 行,第 $i$ 行包含 $m$ 个空格分隔的整数 $B_{i1}, B_{i2}, \ldots, B_{im}$ —— 若第 $i$ 行第 $j$ 列的格子为空地, $B_{ij}$ 为该格变为障碍物后投放的方案数;否则 $B_{ij} = 0$。

    样例

    样例 1 输入
    1
    2
    3
    2 4
    0 0 0 0
    0 0 0 1
    样例 1 输出
    1
    2
    14 13 10 22
    15 11 17 0
    样例 1 解释

    以第 $2$ 行第 $1$ 列的空地格为例,其变为障碍物后的网格如下图,其中白色格子代表空地,黑色格子代表障碍物。

    15 种方案如下图所示,不同颜色代表不同运输机的投放位置。

    样例 2 输入
    1
    2
    3
    4
    5
    4 5
    0 0 0 1 1
    1 0 0 0 1
    1 0 0 0 0
    0 0 0 0 0
    样例 2 输出
    1
    2
    3
    4
    1882 827 1523 0 0
    0 1189 791 1529 0
    0 1106 979 823 1315
    1810 899 1136 1075 1189

    数据范围与提示

    对于所有数据,有 $1 \leq n, m \leq 17$,$A_{ij} \in {0, 1}$。

    子任务编号 分值 $n$ $m$
    1 10 $\leq 2$ $\leq 17$
    2 8 $\leq 5$ $\leq 5$
    3 6 $\leq 9$ $\leq 9$
    4 9 $\leq 12$ $\leq 12$
    5 17 $\leq 15$ $\leq 15$
    6 17 $\leq 16$ $\leq 16$
    7 33 $\leq 17$ $\leq 17$

    “Von allem Anfang an bin ich nur verraten und betrogen worden!”

    题面与史实不尽相符。


    来自 CodePlus 2018 3 月赛,清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
    Credit:idea/吕时清 命题/吕时清 验题/吕欣,王聿中
    Git Repo:https://git.thusaac.org/publish/CodePlus3
    感谢腾讯公司对此次比赛的支持。


    题解

    首先我们可以想到这道题一定是用插头$DP$

    那么我们定义插头的状态 $1$ 为这个方向的格子与它为一架运输机投放
    然后转移时注意一下合法性就可以了, 很是简单的一道 $DP$
    这样的话枚举每一个格子为障碍。
    时间复杂度为 $O(n^2m^22^{m+1})$

    但是这样并不能 $A$ 掉这道题, 事实上, 在 LibreOJ 它只能拿到 $33$ 分的好成绩。

    33pts


    正解
    我们发现每次只有一个点不同
    然后我们可以考虑合并。

    我们正反分别进行一次插头$DP$ 将所有的状态储存下来
    在考虑一个块的时候

    将正反的 $DP$ 值乘起来就好了
    需要判断一下合法性

    时间复杂度$O(nm2^{m+1}+nm2^{m+1})$

    没了

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    #include <cstdio>
    #include <stdint.h>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    inline int read()
    {
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
    }
    const int MAXN = 200000, BASE = 76543;
    const int32_t MOD = 1e9 + 7;
    int f[20][20][(1 << 18) + 1], g[20][20][(1 << 18) + 1];
    int a[20][20], ans[20][20];
    // int tmp[(1 << 18) + 1];
    int DP1(int n, int m)
    {
    // f[0].clear();
    int M = (1 << (m + 1)) - 1;
    f[1][0][0] = 1;
    // int now = 0;
    // int Ans = 0;
    register int32_t k = 0, i, j;
    for (i = 1; i <= n; i++)
    {
    for (j = 1; j <= m; j++)
    {
    // now ^= 1;
    // f[now].clear();
    for (k = 0; k <= M; k++)
    {
    int S = k;
    int Sum = f[i][j - 1][k];
    char L = (S >> (j - 1)) & 1, U = (S >> j) & 1;
    if (a[i][j])
    {
    if (L == 0 && U == 0)
    f[i][j][S] = (f[i][j][S] + Sum) % MOD;
    continue;
    }
    else if (L == 1 && U != 1)
    {
    int nxt = S ^ (1 << (j - 1));
    f[i][j][nxt] = (f[i][j][nxt] + Sum) % MOD;
    }
    else if (L != 1 && U == 1)
    {
    int nxt = S ^ (1 << j);
    f[i][j][nxt] = (f[i][j][nxt] + Sum) % MOD;
    }
    else if (L != 1 && U != 1)
    {
    int nxt = S ^ (1 << (j - 1));
    if (i != n)
    f[i][j][nxt] = (f[i][j][nxt] + Sum) % MOD;
    nxt = S ^ (1 << j);
    if (j != m)
    f[i][j][nxt] = (f[i][j][nxt] + Sum) % MOD;
    f[i][j][S] = (f[i][j][S] + Sum) % MOD;
    }
    // if (S == 0)
    // Ans += Sum;
    }
    }
    for (int k = 0; k <= M; k++)
    f[i + 1][0][k << 1] = f[i][m][k];
    // for (k = 0; k < f[now].p; k++)
    // f[now].v[k].Id <<= 1;
    }
    return f[n][m][0];
    }

    // f->g
    int DP2(int n, int m)
    {
    // f[0].clear();
    int M = (1 << (m + 1)) - 1;
    g[n][m + 1][0] = 1;
    // int now = 0;
    // int Ans = 0;
    register int32_t k = 0, i, j;
    for (i = n; i >= 1; i--)
    {
    for (j = m; j >= 1; j--)
    {
    // now ^= 1;
    // f[now].clear();
    for (k = 0; k <= M; k++)
    {
    int S = k;
    int Sum = g[i][j + 1][k];
    char L = (S >> (j - 1)) & 1, U = (S >> j) & 1;
    if (a[i][j])
    {
    if (L == 0 && U == 0)
    g[i][j][S] = (g[i][j][S] + Sum) % MOD;
    continue;
    }
    else if (L == 1 && U != 1)
    {
    int nxt = S ^ (1 << (j - 1));
    g[i][j][nxt] = (g[i][j][nxt] + Sum) % MOD;
    }
    else if (L != 1 && U == 1)
    {
    int nxt = S ^ (1 << j);
    g[i][j][nxt] = (g[i][j][nxt] + Sum) % MOD;
    }
    else if (L != 1 && U != 1)
    {
    int nxt = S ^ (1 << (j - 1));
    if (j != 1)
    g[i][j][nxt] = (g[i][j][nxt] + Sum) % MOD;
    nxt = S ^ (1 << j);
    if (i != 1)
    g[i][j][nxt] = (g[i][j][nxt] + Sum) % MOD;
    g[i][j][S] = (g[i][j][S] + Sum) % MOD;
    }
    // if (S == 0)
    // Ans += Sum;
    }
    }
    for (int k = M; k >= 0; k--)
    // {
    g[i - 1][m + 1][k >> 1] = g[i][1][k];
    // printf ("%d %d %d %d\n", k >> 1, k, g[i - 1][m + 1][k >> 1], g[i][1][k]);
    // }
    // for (k = 0; k < f[now].p; k++)
    // f[now].v[k].Id <<= 1;
    }
    return g[1][1][0];
    }
    int main()
    {

    char n = read(), m = read();
    register int i, j, k;
    for (i = 1; i <= n; i++)
    for (j = 1; j <= m; j++)
    a[i][j] = read();
    DP1(n, m), DP2(n, m);
    int M = (1 << (m + 1)) - 1;
    for (i = 1; i <= n; i++)
    for (j = 1; j <= m; j++)
    {
    if (a[i][j]) continue;
    int Sum = 0;
    for (k = 0; k <= M; k++)
    {
    char L = (k >> (j - 1)) & 1, U = (k >> j) & 1;
    if (L == 0 && U == 0)
    (Sum += 1ll * f[i][j - 1][k] * g[i][j + 1][k] % MOD) %= MOD;
    }
    ans[i][j] = Sum;
    }
    for (i = 1; i <= n; i++)
    for (j = 1; j <= m; j++)
    printf ("%d%c", ans[i][j], " \n"[j == m]);
    // while (1);
    }

    本文作者 : NekoMio
    知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
    本文链接 : https://www.nekomio.com/2018/04/13/146/

    本文最后更新于 天前,文中所描述的信息可能已发生改变