暴力部分

$n\leq 20$，一边搜索一边判断，或者搜完判断都可以。

$k=m$，直接输出$k!$即可，正确性懒得证。

$k=2$，考虑直接状压$dp_{i,sta}$表示考虑到了$i$，前$m$个位置分别是$0$还是$1$的方案数。

$m\leq 5$，还是直接状压，只不过状态变成了$4^m$。

正解

考虑这样一件事，比如你当前$m$个位置对应的酒分别是1,1,2,1,3,2,3。

实际上你只需要记*,*,*,1,*,2,3就可以了，也就是只保留每种酒最后一次出现的位置。反正后续对答案的贡献都一样。

再多想一步：其实*,*,*,1,*,2,3与*,*,*,3,*,1,2后续的贡献也一样，对吧。

所以我们直接记成0001011即可。

$dp_{i,sta}$表示考虑到$i$了，当前每一种酒最后一次出现的位置是$sta$的方案数。

对于每一次转移，考虑是哪一个$1$被替换到最前面即可。

初始状态可以从$dp_{m,sta}$开始转移，初始状态的方案数计算见代码。

复杂度$O(n2^m)$。

#include<bits/stdc++.h>
#define ll long long
#define maxn 100005
#define mod 998244353
using namespace std;
int dp[maxn][1<<10];
int n,k,m;
basic_string<int> ok;
void add(int &x,int y) {x=(x+y)%mod; return;}
int cal(int sta)
{
	ll ret=1,num=0;
	for (int i=0;i<m;i++)
	{
		if ((sta>>i)&1) {ret=ret*(k-num)%mod; num++;}
		else ret=ret*num%mod;
	}
	return ret;
}
int main()
{
	cin>>n>>k>>m;
	for (int sta=1;sta<(1<<m);sta+=2)
	if (__builtin_popcount(sta)==k)
	{
		dp[m][sta]=cal(sta);
		ok+=sta;
	}
	int S=(1<<m)-1;
	for (int i=m;i<n;i++)
	for (int j:ok)
	if (dp[i][j])
	{
		//必须得搞定这个位置了 
		if ((j>>(m-1))&1) add(dp[i+1][((j<<1)&S)|1],dp[i][j]);
		else
		{
			for (int w=0;w<m;w++)
			if ((j>>w)&1)
				add(dp[i+1][((j^(1<<w))<<1)|1],dp[i][j]);
		}
	}
	int ans=0;
	for (int sta:ok) add(ans,dp[n][sta]);
	cout<<ans<<endl;
}