Codeforces 1239A:Ivan the Fool and the Probability Theory 题解

主要思路

首先需要知道一个性质:如果第一行和第一列确定,那么这个方案就已经完全确定了。这个可以用归纳法证明:

证明  如果格子\((i – 1, j)\)、\((i, j – 1)\)和\((i – 1, j – 1)\)的颜色确定,那么显然\((i, j)\)的颜色就能被唯一确定。如果第一行和第一列可以被确定,那么根据上述描述,便可生成一个唯一的方案。

所以欲记录方案的个数,那么就要记录合法的第一行和第一列的方案数。这样我们把问题转换到了长条上。

设置\(dp[i][0/1][0/1]\)为到第\(i\)位是否连续、最后一位填的数字。那么转移非常自然,可以自行推导(确实啊)。

最后答案就是把所有情况加起来,再减去非法的两种情况(也就是左上角的三格同色的情况)。

代码

// CF1239A.cpp
#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7, MAX_N = 1e5 + 200;

int n, m, dp[MAX_N][2][2];

int main()
{
    scanf("%d%d", &n, &m);
    dp[1][1][0] = dp[1][0][0] = 1;
    for (int i = 2; i <= max(n, m); i++)
    {
        // white settings;
        // both white;
        dp[i][0][1] = dp[i - 1][0][0];
        // the prev one is black or double black;
        dp[i][0][0] = (1LL * dp[i - 1][1][0] + 1LL * dp[i - 1][1][1]) % mod;
        // black settings;
        // both black;
        dp[i][1][1] = dp[i - 1][1][0];
        // double or single;
        dp[i][1][0] = (1LL * dp[i - 1][0][0] + 1LL * dp[i - 1][0][1]) % mod;
    }
    int ans = 0;
    for (int i = 0; i <= 1; i++)
        for (int j = 0; j <= 1; j++)
            ans = (1LL * ans + 1LL * dp[n][i][j] + 1LL * dp[m][i][j]) % mod;
    ans -= 2;
    while (ans < 0)
        ans += mod;
    ans %= mod;
    printf("%d", ans);
    return 0;
}

4 条评论

  1. 我不太懂为什么要减二呢,刚开始
    0 0 1 1
    0 1
    这样,后面还是由这个推出来的,我怎么感觉不仅对答案共享了2

发表评论

邮箱地址不会被公开。 必填项已用*标注