hihoCoder [Offer收割]编程练习赛38 C 小球染色

题目链接https://hihocoder.com/problemset/problem/1651

题意:略。

思路:我们设dp[i][j]为前i个球有j个球末尾连续颜色相同的方案数,可以知道当j==1时,dp[i][j]=\\sum dp[i-1][l]*(m-1)(1\\leq l \\leq k-1),其他时候dp[i][j]=dp[i-1][j-1],如此转移即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P=1000000007;
const int maxn=1005;
int n,m,k;
ll ans,dp[maxn][maxn];
int main(){
    scanf("%d%d%d",&n,&m,&k);
    dp[1][1]=m;
    for (int i=2;i<=n;i++){
        for (int j=1;j<k;j++){
            (dp[i][1]+=dp[i-1][j]*(m-1)%P)%=P;
        }
        for (int j=2;j<k;j++){
            dp[i][j]=dp[i-1][j-1];
        }
    }
    for (int i=1;i<k;i++){
        (ans+=dp[n][i])%=P;
    }
    printf("%lld\n",ans);
    return 0;
}

发表评论

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