CF1239A Ivan the Fool and the Probability Theory


题意简述:

给定一个 $n\cdot m$ 的方格图,每个格子可以被染成黑色或白色,且与其相邻的四个格子中至多只有一个与其颜色相同,求方案数。

题解:

我们可以一行一行的考虑 首先假如第一行存在连续的两个1 那么后面的状态就全部可以推出 因为下面两个肯定是0 然后所有状态就可以一步步推出来 相邻没有连续的只有一种情况即101010…注意我们此时只考虑一个大类 实际上01可以取反所以最后算出的状态要乘2

在101010…的情况下 第一行没有影响 所以第一列会产生影响 这种情况和之前一样 所以我们只要考虑第一行或者第一列合法的有多少状态即可 要么一个要么两个 其实这就是斐波那契数列 当然我们也可以写一个dp

f[i][0]表示第i个是黑色 f[i][1]表示第i个是白色 有如下dp式

$f[i][0]=f[i-1][1]+f[i-2][1]$

$f[i][1]=f[i-1][0]+f[i-2][0]$

$f[0][0]=f[0][1]=f[1][1]=f[0][0]=1$

当然这个dp式的值其实就是斐波那契

然后我们算出$f[n]$注意10101..的情况要去掉给列考虑 所以有$f[n]-1$个状态 列又有$f[m]$个状态 最后01取反 所以状态共有$(f[n]+f[m]-1)\cdot 2$

注意由于有减法所以模意义下有可能会变成负数 所以需要(x%p+p)%p这样的操作

AC代码:

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#define ll long long
#define F(i,a,b) for(int i=(a);i<=(b);i++)
#define mst(a,b) memset((a),(b),sizeof(a))
#define PII pair<int,int>
using namespace std;
template<class T>inline void read(T &x) {
    x=0; int ch=getchar(),f=0;
    while(ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    if(f)x=-x;
}
const int inf=0x3f3f3f3f;
const int mod=1e9+7; 
const int N=100000;
const int maxn=100050;
ll f[maxn][2];
ll n,m;
void init(int n)
{
    f[1][1]=1,f[1][0]=1,f[0][0]=1,f[0][1]=1;
    for(int i=2;i<=n;i++)
    {
        f[i][1]=(f[i-1][0]+f[i-2][0])%mod;
        f[i][0]=(f[i-1][1]+f[i-2][1])%mod;
    }

}
int main()
{
    init(N);
    cin>>n>>m;
    cout<<((((f[n][1]-1+f[m][1])*2)%mod+mod)%mod)<<endl;
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
P2312 解方程 P2312 解方程
题意简述:已知方程:$a_0+a_1x+a_2x^2+\cdots+a_nx^n=0$求该方程在$[1,m]$内的正整数解 $(0<n\leq100,m\leq10^6,|a_i|\leq10^{10000})$ 题解:首先看到那么
2019-11-16
下一篇 
CF1257C Dominated Subarray CF1257C Dominated Subarray
题意简述:给定一个序列 找出其中最短的连续子段使得子段中只有一个众数(子段长度大于等于2) 题解:首先考虑一下假如有一段连续相同的数字 那么答案就一定是2 即从连续的一段中随便挑连续的两个 那么众数就是这个数 那么接下来只剩下没有连续相同
2019-11-14
  目录