Codeforces 1239A. Ivan the Fool and the Probability Theory

发布时间：2020-12-14 04:39:08 所属栏目：大数据来源：网络整理

导读：传送门注意到连续两个格子如果有相同颜色那么一路过去的都可以确定比如一开始染了这两个位置： ? 然后发现后面整片过去都可以确定： ? 对于横着的情况也是一样，然后就会发现不可能出现横着两个和竖着两个同时都有的情况，因为这样一定会冲突，就一定不合

传送门

注意到连续两个格子如果有相同颜色那么一路过去的都可以确定

比如一开始染了这两个位置：

?然后发现后面整片过去都可以确定：

?对于横着的情况也是一样，然后就会发现不可能出现横着两个和竖着两个同时都有的情况，因为这样一定会冲突，就一定不合法了

（自己画一下就知道了）

那么现在只要对行列分别计算即可，直接设 $f[i][0/1][0/1]$ 表示前 $i$ 个位置，当前位置为 $0/1$ 上一个位置为 $0/1$ 时的方案数

那么转移十分显然，然后答案就是行任意放的方案 $sum_{i=0}^{1}sum_{j=0}^{1}f[n][i][j]$ 加上列任意放的方案?$sum_{i=0}^{1}sum_{j=0}^{1}f[m][i][j]$ 减 $2$

减 $2$ 是因为黑白染色情况下的方案会被行和列都算到，要减去多算的次数

然后就可以过了，但是事实上如果直接设 $g[i]=sum_{i=0}^{1}sum_{j=0}^{1}f[n][i][j]$ ，然后分析原本 $f$ 的方程，那么你会发现 $g[i]$ 恰好等于 $g[i-1]+g[i-2]$

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
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<<1)+(x<<3)+(ch^48); ch=getchar(); }
    return x*f;
}
const int N=2e5+7,mo=1e9+7;
inline int fk(int x) { return x>=mo ? x-mo : x; }
int n,m,f[N][2][2];
int main()
{
    n=read(),m=read(); int mx=max(n,m);
    if(n==1&&m==1) { printf("2n"); return 0; }
    f[2][0][0]=f[2][0][1]=f[2][1][0]=f[2][1][1]=1;
    for(int i=3;i<=mx;i++)
    {
        f[i][0][0]=f[i-1][0][1];
        f[i][0][1]=fk(f[i-1][1][0]+f[i-1][1][1]);
        f[i][1][0]=fk(f[i-1][0][0]+f[i-1][0][1]);
        f[i][1][1]=f[i-1][1][0];
    }
    if(n>m) swap(n,m);
    if(n==1) { printf("%dn",fk(fk(f[m][0][0]+f[m][0][1]) + fk(f[m][1][0]+f[m][1][1])) ); return 0; }
    int ans=fk(fk(f[m][0][0]+f[m][0][1]) + fk(f[m][1][0]+f[m][1][1]));
    ans=fk(ans-2+mo);
    ans=fk(ans+ fk(fk(f[n][0][0]+f[n][0][1]) + fk(f[n][1][0]+f[n][1][1])));
    printf("%dn",ans);
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!