https://codeforces.com/problemset/problem/1081/C
这道题是不会的，我只会考虑 $k=0$ 和 $k=1$ 的情况。
$k=0$ 就是全部同色， $k=1$ 就是左边一个色右边一个色， $m(m-1)$ ，再选转折点有 $i-1$ 种 $C_{i-1}^{1} $（ $i$ 个球。 $i-1$ 个空挡都可以插）。
到 $k=2$ 呢？可以是三种不同颜色，也可以是左右左，也就是 $m(m-1)(m-1)$ ，再选转折点有 $C_{i-1}^{2}$ 。
到k=3呢？更复杂了？ $m(m-1)(m-1)(m-1)$ ，中间的用隔板法算，也就是 $C_{i-1}^{3}$ ？
所以答案其实就是 $m(m-1)^kC_{n-1}^k$ ，是组合数学？
隔板法就是：（可以为空的情况）给每组默认加上一个小球，然后隔板就可以选所有球的间隔。（不能为空的情况：）选所有球的间隔
ll qpow(ll x,ll n){
ll res=;
while(n){
if(n&)
res=res*x%p;
x=x*x%p;
n>>=;
}
return res;
}
void init(int n){
fac[]=;
for(int i=;i<=n;i++){
fac[i]=fac[i-]*i%p;
}
invfac[n]=qpow(fac[n],p-);
//费马小定理
for(int i=n;i>=;i--){
invfac[i-]=invfac[i]*i%p;
}
//线性求阶乘逆元
}
ll C(int n,int m){
return fac[n]*invfac[n-m]%p*invfac[m]%p;
}dp解法： $f[i][j]=f[i-1][j]+f[i-1][j-1]$ ，以位置 $i$ 为结尾的，有j次转折，分在此转折和跟随左侧颜色两种情况
好不容易抄了一个线性求 $invfac$ ，居然费马小定理的时候传入一个 $n$ 而不是 $fac[n]$ ，我是服气了的，最后还忘记把 $2$ 改成 $k$ ，我大概是智障吧。
#include<bits/stdc++.h>
using namespace std;
#define ll long long ll dp[][]={}; //dp[i][k]以i为结尾的，有k块砖与左边的颜色不一样
ll p=; ll pow_mm1[];
ll fac[];
ll invfac[]; ll qpow(ll x,ll n){
ll res=;
while(n){
if(n&)
res=res*x%p;
x=x*x%p;
n>>=;
}
return res;
} void init(int n){
fac[]=;
for(int i=;i<=n;i++){
fac[i]=fac[i-]*i%p;
}
invfac[n]=qpow(fac[n],p-);
//费马小定理
for(int i=n;i>=;i--){
invfac[i-]=invfac[i]*i%p;
}
//线性求阶乘逆元
} ll C(int n,int m){
return fac[n]*invfac[n-m]%p*invfac[m]%p;
} int n,m,k;
int main(){
init(); pow_mm1[]=;
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=;i++){
pow_mm1[i]=pow_mm1[i-]*(m-)%p;
} /*for(int i=1;i<=n;i++){
dp[i][0]=m;
//都是同一种颜色
} for(int i=1;i<=n;i++){
dp[i][1]=m*(m-1)%p*(i-1)%p;
//左边的至少一块砖其中一种颜色，右边的另一种颜色，左边有1~i-1块砖
for(int k=2;k<=i-1;k++){
dp[i][k]=(m*pow_mm1[k])%p*C(i-1,k)%p;
}
}
*/ //dp[i][k]=(m*pow_mm1[k])%p*C(i-1,k)%p;
printf("%lld\n",(m*pow_mm1[k])%p*C(n-,k)%p); }
拓展阅读：组合数学的水题？https://www.cnblogs.com/kuangbin/archive/2012/08/28/2661066.html
2019-01-16