Bicolorings - codeforce

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

导读：题解：dp[ i ][ k ][0 ~ 3] ：表示第 i 列状态为s（s = 0，1，2，3）时总的联通个数。注意：dp[ i ][ k ][ 1 ] 和 dp[ i ][ k ][ 2 ] 的转移。 const int N = 1005 ; const int mod = 998244353 ; int n,k;LL dp[N][ 2 * N][ 4 ]; int main(){ cin n k; dp[

题解：dp[ i ][ k ][0 ~ 3] ：表示第 i 列状态为s（s = 0，1，2，3）时总的联通个数。

注意：dp[ i ][ k ][ 1 ] 和 dp[ i ][ k ][ 2 ] 的转移。

const int N = 1005;
const int mod = 998244353;

int n,k;
LL dp[N][2 * N][4];

int main()
{
    cin >> n >> k;
    dp[1][1][0] = 1;
    dp[1][1][3] = 1;
    dp[1][2][1] = 1;
    dp[1][2][2] = 1;
    Rep(i,2,n) Rep(j,1,2 * i) {
        dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1] + dp[i - 1][j][2] + dp[i - 1][j - 1][3];
        dp[i][j][3] = dp[i - 1][j - 1][0] + dp[i - 1][j][1] + dp[i - 1][j][2] + dp[i - 1][j][3];
        if (j > 1) dp[i][j][1] = dp[i - 1][j - 1][0] + dp[i - 1][j][1] + dp[i - 1][j - 2][2] + dp[i - 1][j - 1][3];
        if (j > 1) dp[i][j][2] = dp[i - 1][j - 1][0] + dp[i - 1][j - 2][1] + dp[i - 1][j][2] + dp[i - 1][j - 1][3];
        rep(t,0,4) dp[i][j][t] %= mod;
    }
    LL res = (dp[n][k][0] + dp[n][k][1] + dp[n][k][2] + dp[n][k][3]) % mod;
    cout << res << endl;
    return 0;
}

（编辑：李大同）

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