题目大意：
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[2005][2005]; LL mod_pow(LL x,LL n) { LL res=1LL; while(n) { if(n&1) res=res*x%mod; x=x*x%mod; n>>=1; } return res%mod; } int main() { while(~scanf("%I64d%I64d%I64d",&n,&m,&k)) { memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) dp[i][0]=1LL; for(int i=2;i<=n;i++) for(int j=1;j<i && j<=k;j++) dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])%mod; LL one=1LL*m*mod_pow(m-1LL,k)%mod; printf("%I64d\n",one*dp[n][k]%mod); } return 0; } View Code
转载于:https://www.cnblogs.com/zquzjx/p/10129480.html
相关资源：JAVA上百实例源码以及开源项目