题目描述
莫斯科吹的寒风 / 仿佛昨日那场梦 / 啊 你还会记得我吗
1941.12.
寒冷刺骨的天气、疲惫不堪的军队……包围首都的作战计划陷入了困境。空军或许是拯救战况的最后希望了,元首 Adolf 想道。
在一个 的网格区域中存在一个陆军单位需要补给,区域中的每个格子为空地或障碍物中的一种。航空舰队需要派遣若干运输机前往此区域,每一架运输机可以向两个相邻(有一条公共边)的空地投放物资。为防止不必要的损坏,一个标记为空地的格子至多只能得到一次投放。
由于天气原因,陆军单位所在的确切位置并不能确定。因此元首想知道,对于每个空地格子,当陆军单位在其中(视作障碍物)时,用若干(可以为 )架运输机向其余空地投放任意数量的物资的不同方案数。两个投放方案不同,当且仅当存在一个格子在一个方案中被投放而另一方案中未被投放,或存在两个被投放的格子,在一个方案中被同一架运输机投放而在另一方案中非然。若仍有疑问,请参考「样例 1 解释」。
你需要编写程序帮助元首计算这些值对 取模的结果。
输入格式
从标准输入读入数据。
- 第 行:两个空格分隔的正整数 —— 网格区域的行数和列数。
- 接下来 行:其中第 行包含 个空格分隔的整数 —— 其中 表示第 行第 列的格子为空地; 表示该格为障碍物。
输出格式
输出到标准输出。
对于每组数据输出 行,第 行包含 个空格分隔的整数 —— 若第 行第 列的格子为空地, 为该格变为障碍物后投放的方案数;否则 。
样例
样例 1 输入
2 40 0 0 00 0 0 1
样例 1 输出
14 13 10 2215 11 17 0
样例 1 解释
以第 行第 列的空地格为例,其变为障碍物后的网格如下图,其中白色格子代表空地,黑色格子代表障碍物。
15 种方案如下图所示,不同颜色代表不同运输机的投放位置。
样例 2 输入
4 50 0 0 1 11 0 0 0 11 0 0 0 00 0 0 0 0
样例 2 输出
1882 827 1523 0 00 1189 791 1529 00 1106 979 823 13151810 899 1136 1075 1189
数据范围与提示
对于所有数据,有 ,。
子任务编号 | 分值 | ||
---|---|---|---|
1 | 10 | ||
2 | 8 | ||
3 | 6 | ||
4 | 9 | ||
5 | 17 | ||
6 | 17 | ||
7 | 33 |
“Von allem Anfang an bin ich nur verraten und betrogen worden!”
题面与史实不尽相符。
来自 CodePlus 2018 3 月赛,清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit:idea/吕时清 命题/吕时清 验题/吕欣,王聿中
Git Repo:https://git.thusaac.org/publish/CodePlus3
感谢腾讯公司对此次比赛的支持。
题解
首先我们可以想到这道题一定是用插头
那么我们定义插头的状态 为这个方向的格子与它为一架运输机投放
然后转移时注意一下合法性就可以了, 很是简单的一道
这样的话枚举每一个格子为障碍。
时间复杂度为
但是这样并不能 掉这道题, 事实上, 在 LibreOJ 它只能拿到 分的好成绩。
正解
我们发现每次只有一个点不同
然后我们可以考虑合并。
我们正反分别进行一次插头 将所有的状态储存下来
在考虑一个块的时候
将正反的 值乘起来就好了
需要判断一下合法性
时间复杂度
没了
#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->gint 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);}