Description
On his free time, Chouti likes doing some housework. He has got one new task, paint some bricks in the yard.
There are n bricks lined in a row on the ground. Chouti has got m paint buckets of different colors at hand, so he painted each brick in one of those m colors.
Having finished painting all bricks, Chouti was satisfied. He stood back and decided to find something fun with these bricks. After some counting, he found there are k bricks with a color different from the color of the brick on its left (the first brick is not counted, for sure).
So as usual, he needs your help in counting how many ways could he paint the bricks. Two ways of painting bricks are different if there is at least one brick painted in different colors in these two ways. Because the answer might be quite big, you only need to output the number of ways modulo 998244353.
Input
The first and only line contains three integers n, m and k (1≤n,m≤2000,0≤k≤n−1) — the number of bricks, the number of colors, and the number of bricks, such that its color differs from the color of brick to the left of it.
Output
Print one integer — the number of ways to color bricks modulo 998244353 .
Sample Input
Input 3 3 0 Output 3 Input 3 2 1 Output 4
题意：n代表的有n个格子，m代表有m种颜色，k代表有k个格子的左边第一个是与他不同的颜色
思路： 1.组合数学 因为第一个格子不会影响其他的格子，所以第一个格子有m种颜色，从剩的n-1个格子中挑选k个，因为这个格子与左边的不同，所以这个格子能取的颜色是m-1种 所以公式为 m ∗ C k n − 1 ∗ ( m − 1 ) k m*C_k^{n-1}*(m-1)^k m∗Ckn−1∗(m−1)k
C k n − 1 C_k^{n-1} Ckn−1遵循杨辉三角，即 C a b = C a − 1 b + C a − 1 b − 1 C_a^b=C_{a-1}^b+C_{a-1}^{b-1} Cab=Ca−1b+Ca−1b−1
代码：
#include <iostream> #include <cstring> #include <cstdio> #include <cstdlib> #include <map> #include<algorithm> #define mod 998244353 #define memset(a,b) memset(a,b,sizeof(a)) #define ll long long using namespace std; int c[2005][2005]; ll quick_pow(ll a, ll b) { ll base = a,ans=1; while(b) { if(b & 1) ans = ((ans%mod) * (base%mod))%mod; base = ((base%mod)*(base%mod))%mod; b /= 2; } return ans; } int main() { //init(); ll n,m,k; memset(c,0); scanf("%lld %lld %lld",&n,&m,&k); ll ans; ll sum=quick_pow(m-1,k); for(int i=1; i<=2000; i++) for(int j=0; j<=2000; j++) { if(j == 1) c[i][j] = i; else if(j == 0) c[i][j] = 1; else c[i][j] = (c[i-1][j]+c[i-1][j-1])%mod; } //cout<<c[5]<<endl; ll sum2; if(k == 0) sum2 = 1; else sum2 = c[n-1][k]; ans = (((m * sum)%mod)*sum2)%mod; printf("%lld\n",ans%mod); return 0; }2.DP dp[ i ][ j ]代表一共有i个格子，j个符合条件的 所以状态转移方程为： dp[ i ][ j ] = dp[ i-1 ][ j ] + dp[ i-1 ][ j-1 ]*(m-1)
代码：
#include <iostream> #include <cstring> #include <cstdio> #include <cstdlib> #include <map> #include<algorithm> #define mod 998244353 #define memset(a,b) memset(a,b,sizeof(a)) #define ll long long using namespace std; ll dp[2005][2005]; int main() { //init(); int n,m,k; memset(dp,0); scanf("%d %d %d",&n,&m,&k); dp[1][0] = 1; for(int i=1; i<=2000; i++) for(int j=0; j<=2000; j++) { if(j == 0) dp[i][j] = m; else dp[i][j] = (dp[i-1][j]%mod + ((dp[i-1][j-1]%mod)*(m-1))%mod)%mod; } printf("%lld\n",dp[n][k]); return 0; }