本题的大意是一共有N个放格排列，每一个排列都可以有M种颜色，需要求解涂有相同颜色的对数不超过K对，可以考虑从N个中选择i个相邻的元素是一样的，这个i的范围是从0～k，之后可以发现第一个一定是M种选择，剩下的不同颜色的选择是$(M-1)^(N-1-i)$需要注意的是除法没有取模，所以需要使用到逆元 ``` #include<cstdio> #include<iostream> #include<vector> #include<map> #include<cstring> #include<array> #include<queue> #include<algorithm> #include<set> #include<cmath> using namespace std; using i64=long long; //using i128=__int128; //const i64 INF=1e18; const int mod=998244353; //const int N=1e9+7; const int N=2e5+10; i64 fact[N],invfact[N]; i64 qmi(i64 a,i64 b){ i64 res=1; while(b){ if(b&1)res=res*a%mod; a=a*a%mod; b>>=1; } return res; } void init(){ fact[0]=invfact[0]=1; for(int i=1;i<=N;i++)fact[i]=i*fact[i-1]%mod; invfact[N]=qmi(fact[N],mod-2)%mod; for(int i=N-1;i>=0;i--){ invfact[i]=invfact[i+1]*(i+1)%mod; } } void solve(){ int n,m,k; cin>>n>>m>>k; i64 ans=0; for(int i=0;i<=k;i++){ if(n-i-1<0)break; ans=(ans+m*qmi(m-1,n-i-1)%mod*fact[n-1]%mod*invfact[i]%mod*invfact[n-i-1]%mod)%mod; } cout<<ans<<'\n'; } int main(){ init(); int _=1; //cin>>_; while(_--)solve(); return 0; } ```