Codeforces Round #594 (Div. 1) Ivan the Fool and the Probability Theory

题意：给你一个NxM的图，让你求有多少符合 “一个格子最多只有一个同颜色邻居”的图？

题解：首先我们可以分析一维，很容易就可以知道这是一个斐波那契计数

　　　因为dp[1][m]可以是dp[1][m-1]添加一个和结尾不同颜色的块，或者dp[1][m-2]加上两个和结尾不同颜色的块

　　　为什么dp[1][m-1]不可以添加一个和结尾颜色相同的块呢？因为这样情况就和dp[1][m-2]重叠了。

　　　接着我们再分析多维情况

　　　假设我们有一个3x6的图

　　　第一种情况：

　　　第一行中有相邻同色块，例如 100101

　　　那么很明显，第二行只能是 011010，第三行只能是100101，也就是第一行确定了这个图

　　　第二种情况：

　　　第一行中没有相邻同色块，例如101010

　　　那么很明显，第二行可以选择 101010 或者 010101，第三行可以选择101010或者010101

　　　如果我们一直取与上一行完全相反的，那么就是

　　　101010

　　　010101

　　　101010

　　　再结合第一种情况，那么对答案的贡献就是 dp[1][m]。

　　　除此以外，那么如果我们取和上一行完全相同的情况还没有计入，这时我们可以把图旋转一下，变成6x3的图

　　　同理，这样对答案的贡献就是 dp[1][n]，但是由于6x3和3x6的完全黑白相间的图

　　　101010　　010101　　　 101 　　010

　　　010101　　101010　　　 010　　101

　　　101010　　010101　　　 101　　010

　　　　　　　　　　　　　　　 010　　101

　　　　　　　　　　　　　　　 101　　010

　　　　　　　　　　　　　　　 010　　101

　　这两种情况其实是相同的，所以最终答案需要-2 ，也就是 ans= dp[1][n]+dp[1][m]-2

//freopen("in.txt", "r", stdin);

#include <bits/stdc++.h>

#include<unordered_set>

using namespace std;

typedef double dou;

typedef long long LL;

typedef pair<int, int> pii;

typedef map<int, int> mii;

#define pai acos(-1.0)

#define M 200050

#define inf 0x3f3f3f3f

#define mod 1000000007

#define IN inline

#define W(a) while(a)

#define lowbit(a) a&(-a)

#define left k<<1

#define right k<<1|1

#define lson L, mid, left

#define rson mid + 1, R, right

#define ms(a,b) memset(a,b,sizeof(a))

#define Abs(a) (a ^ (a >> 31)) - (a >> 31)

#define random(a,b) (rand()%(b+1-a)+a)

#define false_stdio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

LL n, m;

LL ans[M];

int main() {

    false_stdio;

    cin >> n >> m;

    ans[] = , ans[] = ;

    for (int i = ; i <= max(n, m); i++) {

        ans[i] = (ans[i - ] + ans[i - ]) % mod;

    }

    cout << ((ans[n] + ans[m]) % mod + mod - ) % mod << endl;

    return ;

}

巴特西

Codeforces Round #594 (Div. 1) Ivan the Fool and the Probability Theory

最新文章

热门文章