摘要
Title: 4496. 吃水果
Tag: dp
Memory Limit: 64 MB
Time Limit: 1000 ms

4496. 吃水果

题意

n个小朋友站成一排，等着吃水果。
一共有 m种水果，每种水果的数量都足够多。
现在，要给每个小朋友都发一个水果，要求：在所有小朋友都拿到水果后，恰好有 k个小朋友拿到的水果和其左边相邻小朋友拿到的水果不同（最左边的小朋友当然不算数，即最左边的小朋友不包含在 k个小朋友内）。
请你计算，一共有多少种不同的分发水果的方案。
思路

排列组合的做法
dp:
我们设状态, dp[i][j]表示前i位有j个不同的方案数
状态转移(以第i个人和左边人是否不同作为区分点)： $dp[i][j] = dp[i-1][j] + dp[i-1][j-1]*(m-1)$

代码

'''
Author: NEFU AB-IN
Date: 2023-03-20 16:27:52
FilePath: \Acwing\4469\4469.py
LastEditTime: 2023-03-20 17:39:01
'''
read = lambda: map(int, input().split())
from collections import Counter, deque
from heapq import heappop, heappush
from itertools import permutations

N = int(2e3 + 10)
INF = int(2e9)
MOD = 998244353

# dp[i][j]表示前i位有j个不同的方案数
dp = [[0] * N for _ in range(N)]
n, m, k = read()

for i in range(1, n + 1):
    dp[i][0] = m

for i in range(2, n + 1):
    for j in range(1, k + 1):
        dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] * (m - 1) % MOD

print(dp[n][k])

4496. 吃水果

题意

思路

代码