Avito Cool Challenge 2018 C

题目大意：

1*n的格子可以用m种颜色涂色

已知从第2开始到第n个格子有k个格子与其左边的格子颜色不同

求涂色的方案数

相当于把n个格子分成k+1份

可以递推出分成k+1份的不同的方案数（其实递推公式就是组合数递推公式）

也可以隔板法直接求C(n-1,k)

已知所有分法后直接涂色那么第一份可以涂m种颜色

而第二块开始只能涂m-1种因为要和左边那一份的颜色不同

所以C(n-1,k)*m*(m-1)^k

一定要注意取模问题乘法要取模

递推时的加法也要取模啊太粗心了赛后递推加个取模就过了

#include <bits/stdc++.h>

#define LL long long

#define mod 998244353

using namespace std;

LL n,m,k;

LL dp[][];

LL mod_pow(LL x,LL n) {

    LL res=1LL;

    while(n) {

        if(n&) res=res*x%mod;

        x=x*x%mod;

        n>>=;

    } return res%mod;

}

int main()

{

    while(~scanf("%I64d%I64d%I64d",&n,&m,&k)) {

        memset(dp,,sizeof(dp));

        for(int i=;i<=n;i++) dp[i][]=1LL;

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

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

                dp[i][j]=(dp[i-][j]+dp[i-][j-])%mod;

        LL one=1LL*m*mod_pow(m-1LL,k)%mod;

        printf("%I64d\n",one*dp[n][k]%mod);

    }

    return ;

}

巴特西

Avito Cool Challenge 2018 C - Colorful Bricks

最新文章

热门文章