Avito Cool Challenge 2018：C. Colorful Bricks

C. Colorful Bricks

题目链接：https://codeforces.com/contest/1081/problem/C

题意：

有n个横向方块，一共有m种颜色，然后有k个方块的颜色与其左边的颜色不同（第一个除外），问一共有多少染色方案。

题解：

我们首先来考虑一下dp。

设dp(i,j)为当前第i个方块，一共有j个方块与它前面的方块不同的方案个数。

那么转移方程为dp(i,j)=dp(i-1,j-1)*(m-1)+dp(i-1,j)。

代码如下：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MOD = ,N = ;

ll n,m,k;

ll dp[N][N];

int main(){

    cin>>n>>m>>k;

    dp[][]=m;

    for(int i=;i<=n;i++){

        for(int j=;j<i;j++){

            dp[i][j]=dp[i-][j];

            if(j!=) dp[i][j]=(dp[i][j]+dp[i-][j-]*(m-))%MOD;

        }

    }

    cout<<dp[n][k];

    return ;

}

还有一种数学的计数方法。

我们假设已经选定了k种颜色，除开第一个，那么我们就可以直接把2-n的位置进行缩点，缩成有前一个的颜色不等于后一个颜色的点（因为有一些点的颜色是和之前的点颜色相等的，这种对答案没有贡献，取决于之前的那个颜色）。

然后第一个位置有m种情况，之后的每个位置都有m-1种情况。

所以最后答案为C(n-1,k)*m*(m-1)^k。

代码如下：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MOD =  ,N = ;

ll n,m,k;

ll C[N][N];

ll qp(ll a,ll b){

    ll ans = ;

    while(b){

        if(b&) ans=(a*ans)%MOD;

        a=(a*a)%MOD;

        b>>=;

    }

    return ans ;

}

int main(){

    cin>>n>>m>>k;

    C[][]=C[][]=;

    for(int i=;i<=n;i++) C[i][]=;

    for(int i=;i<=n;i++)

        for(int j=;j<=i;j++)

            C[i][j]=(C[i-][j-]+C[i-][j])%MOD;

    ll ans = (C[n-][k]*m)%MOD;

    cout<<ans*qp(m-,k)%MOD<<endl;

    return ;

}

巴特西

Avito Cool Challenge 2018：C. Colorful Bricks

最新文章

热门文章