CF1239A. Ivan the Fool and the Probability Theory

题目:伊凡*与概率论

一看我还以为是真·概率论……

一句话题意:

有一个$n \times m$网格图,每个格可以被涂成白色或黑色,现在定义 ‘随机图’ :每个点的上下左右最多只有一个格与其颜色相同,请计算其数量,对$10^9+7$取模。

题解:

第一次见$Fibonacci$计数。

首先我们思考一下,染色的情况有哪些?

一.完全棋盘

如下,仿佛没啥:

CF1239A. Ivan the Fool and the Probability Theory

二.有两个块卡在一起

发现如果有两个块颜色一致,如果要保证合法就一定将整行列的颜色涂成一致。

CF1239A. Ivan the Fool and the Probability Theory

CF1239A. Ivan the Fool and the Probability Theory

这样就可以实现将二维的棋盘分行列一维化。

现在我们考虑$(1,1)$涂成白色的情况(黑色同理直接$\times 2$即可)

那么第一列的情况就已经确定了(并且后面的列也可以通过第一行的情况推过来)

于是设$f_i$为上述情况下放置$i$列的的情况数。

于是设初态$f_1=1,f_2=2$

如果新放置的这一列和上一列的颜色相同,那么方案数就是$f_{i-2}$

如果和上一列的颜色相反,方案数就是$f_{i-1}$

那么$$f_i=f_{i-1}+f_{i-2}(i \geq 3)$$

这柿子……就是$Fibonacci$吧……

对行列分别求$f$,但是不要忘记把重的情况(完全棋盘)减掉。

于是……

(考场推荐使用打表找规律)

 

#include <iostream>
#include <cstring>
#include <cstdio>
#define LL long long
#define N 111111

using namespace std;

const int Mod=1e9+7;

LL fib[N],m,n;

int main(){
	fib[1]=1,fib[2]=2;
	for(int i=3;i<=100000;i++){
		fib[i]=fib[i-1]+fib[i-2]%Mod;
	}
	cin>>n>>m;
	cout<<2*((fib[n]+fib[m])%Mod-1+Mod)%Mod<<endl;
}
上一篇:nlfsoj 20035 #10851 最大连续子段和 SP1716 GSS3 - Can you answer these queries III


下一篇:题目总结