C - Ivan the Fool and the Probability Theory---div2

题目连接:https://codeforces.com/contest/1248/problem/C

思路：

注意上下两排的关系，如果说上面那一排有两个方格连续，那么他相邻的两排必定和他相反，如果说当前这一排没有连续的两个方格，那么它相邻的两排必定和它相同，因此，当第一排或者第一列确定好了，他下面的也就确定好了。

因此我们只需要考虑当n==1时的规律就行了，，规律为d[i]=d[i-1]+d[i-2]。从第一列往后延续也是可以的，这样就会有d[x]+d[y]对，但是会多加入两组，就是黑白相间的两种，在以行往后延续的时候统计了一次，以列往后延续又统计了一次

因此，我们要减去多统计的（2），答案为（d[x]+d[y]-2)

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod=1e9+;

const int N=1E5+;

ll dp[N];

int main(){

    int n,m;

    scanf("%d%d",&n,&m);

    int x=max(n,m);

    dp[]=;

    dp[]=;

    for(int i=;i<=x;i++) dp[i]=(dp[i-]+dp[i-])%mod;

    ll sum=(dp[n]+dp[m]-+mod)%mod;

    cout<<sum<<endl;

    return ;

}

巴特西

C - Ivan the Fool and the Probability Theory---div2

最新文章

热门文章