ABC167E Colorful Blocks 题解

题目链接：ABC167E Colorful Blocks

题意：

翻译从我们模拟赛搬过来的，稍微有些不一样。

有 $n$ 个小球按照编号为 $1−n$ 从左至右放成一排，你现在要给每个小球染上 $1−m$ 中的颜色，并且满足至多存在 $k$ 对相邻位置上小球的颜色相同。

你需要输出一共有多少种不同的给小球染色的方案，两种染色方案被认为是不同的当且仅当两种方案中存在一个小球被染上了不同的颜色。由于答案可能过大，你需要对 $998244353$ 取模后输出。

$1 \le n,m \le 2\times 10^5,~0\le 0 \le n-1$

简单组合数学。考虑 $k$ 对相邻的情况，

其实就是在前 $n-1$ 个球中选 $k$ 个和它右边的合并

因此答案就是

$$\sum_{i=0}^{k} m \times(m-1)^{n-i-1}\times \dbinom{n-1}{i}$$

前面的 $m \times(m-1)^{n-i-1}$ 可能比较难理解

其实就是一个经典模型：

$n$ 个方格，$m$ 种颜色，相邻不能涂同一种颜色，方案数？

则第一个可以涂 $m$ 种颜色中的任意一种颜色，

剩下的每个都只能涂 $m-1$ 种颜色

故这个模型的答案就是 $m \times (m-1)^{n-1}$

然后就可以理解这个柿子了吧

时间复杂度 $O(n \log N)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e5+15)

const int p=998244353;
int n,m,k,fac[N];
int qpow(int a,int b)
{
    int ans=1,base=a%p;
    while(b)
    {
        if(b&1) ans=ans*base%p;
        base=base*base%p;
        b>>=1;
    }
    return ans;
}
int inv(int x){return qpow(x,p-2);}
void init()
{
    fac[0]=1;
    for(int i=1; i<=n+5; i++)
        fac[i]=fac[i-1]*i%p;
}
void add(int &x,int y){x=(x+y%p)%p;}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m >> k;
    int res=0; init();
    for(int i=0; i<=k; i++)
        add(res,m%p*qpow(m-1,n-i-1)%p*fac[n-1]%p*inv(fac[i])%p*inv(fac[n-i-1])%p);
    cout << res << '\n';
    return 0;
}