ABC167E题解

IsaacX · 2023-05-20 22:31:43 · 题解

Colorful Blocks

题意

题面有点雾，应为：“k 对相邻方格颜色相同”，而不是“k 对相邻颜色的方格”。

思路

考虑恰好有 i 对相邻方格颜色相同时的方案数，最后答案就是所有情况之和。

考虑捆绑法：把相邻的两个颜色相同的方格捆绑成一个方格来看。此时只剩下了 n-i 个方格（因为 2\times i 个方格被捆绑成了 i 个）。

在 n-1 对方格中挑 i 对染为相同颜色，方案数为 C_{n-1}^i。

把 n-i 个方格染上 m 种颜色，且相邻两个不能相同（不然就能合并了）。第一个方格有 m 种染法，剩下 n-i-1 个方格都不能和上一个方格颜色相同，各有 m-1 种染法。方案数为 m\times (m-1)^{n-i+1}。

根据乘法原理，情况为 i 时的总方案数为 C_{n-1}^i\times m\times (m-1)^{n-i+1}。

那么最终答案就是：

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,k,mod=998244353,ans,fac[200005];
int qpow(int x,int y)
{
    int ret=1;
    for(;y;y>>=1,x=x*x%mod)
    {
        if(y&1)
            ret=ret*x%mod;
    }
    return ret;
}
void init()//初始化
{
    fac[0]=1;
    for(int i=1;i<=n;i++)
    {
        fac[i]=fac[i-1]*i%mod;
    }
}
int inv(int x)
{
    return qpow(fac[x],mod-2);//逆元
}
int C(int x,int y)
{
    return fac[x]*inv(y)%mod*inv(x-y)%mod;//求组合数
}
signed main()
{
    scanf("%lld%lld%lld",&n,&m,&k);
    init();
    for(int i=0;i<=k;i++)
    {
        ans=(ans+C(n-1,i)*m%mod*qpow(m-1,n-i-1)%mod)%mod;//统计答案
    }
    printf("%lld",ans);
} 

希望本篇题解能帮到大家！！！