题目:伊凡*与概率论
一看我还以为是真·概率论……
一句话题意:
有一个$n \times m$网格图,每个格可以被涂成白色或黑色,现在定义 ‘随机图’ :每个点的上下左右最多只有一个格与其颜色相同,请计算其数量,对$10^9+7$取模。
题解:
第一次见$Fibonacci$计数。
首先我们思考一下,染色的情况有哪些?
一.完全棋盘
如下,仿佛没啥:
二.有两个块卡在一起
发现如果有两个块颜色一致,如果要保证合法就一定将整行列的颜色涂成一致。
这样就可以实现将二维的棋盘分行列一维化。
现在我们考虑$(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; }