CF1239A
题意
题意很简单,给你一个n*m的方格图.要求每个方格涂黑白两色,要求对于每个方格,不得与超过一个同颜色的相邻(就是上下左右四个邻居中最多只能有一个和它同色的).输出有多少种涂色方式,答案对1e9+7取模
$1<=n,m<=1e6$
图中是n=2,m=3的情况
分析
这个题咋看没有头绪.还是评论区大佬一语惊醒梦中人.
我们先讨论一个简单的问题.
给出一个正整数n,要求生成一个序列,序列中只有1或者2,序列不限制长度,要求输出和为n的种类数.
或者换个说法一个楼梯总共需要走n阶,一次可以走一阶或者两阶,求走n阶的方法数
这是个典型的dp问题.dp[i]表示走i阶的方案数,由于第i阶只能由i-1和i-2阶走上来,所以dp[i]=dp[i-1]+dp[i-2] ,由于dp[1]=1,dp[2]=2,所以dp[i]就是第i个斐波那契数.
我们假设只有一行,行长度为m.如果要求黑白交替填(最后结果记得乘2就是了),一次可填一个或两个方格,求一行的填法.
根据上文的讨论,我们发现是f[m].
我们还发现,如果上一行有两个同色相邻的,那么就其下一行的排列就确定了.
这个需要很敏锐的感知,我是看了答案想了一段时间才看懂.
1
2
3
第一行表示行号,第二行对应的0表示白色,1表示黑色
123456789
011011010
我们发现,对于上图,5,6单元是一定要放白色的,这样会导致7号单元只能是黑色,8号单元只能是白色.也就是说,对于一个连续的块,会导致四周的黑白间隔的块的对应块都是取反的状态,这样的结果就是只要存在着连续的块,其下面一行的块一定是其取反的颜色.这个情况会递推下去,也就是对于(f[m]-1)个情况,只要第一行确定了,整个图就确定了.
但是对于黑白交错(由于选定了开头一定是黑色,这就只有一种情况)的情况,其下一行有两种取法,要么是全部相等,要么是全部相反.我们将黑色开头的黑白交错的行称为b,将白色开头的称为w.
则站在列的角度上,就是拿b,w两种填色(最多有两个连续的),去填充n行
答案自然是f[n]
综上所述,答案应该是2*(f[m]-1+f[n])
非常巧妙.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define mod (int)(1e9 + 7)
ll f[int(1e6) + 10];
void init(int n) {
f[0] = 1;
f[1] = 1;
for (int i = 2; i <= n; ++i) {
f[i] = (f[i - 1] + f[i - 2]) % mod;
}
}
int main() {
int n, m;
cin >> n >> m;
init(max(n, m));
printf("%I64d\n", (2 * (f[n] + f[m] - 1)) % mod);
return 0;
}
