题解：P16685 帽子
Nongwu_
·
·
题解
$2026.6.7$：修改一处严重笔误。
## 题目大意
有 $n$ 顶**各不相同**的帽子，这 $n$ 顶帽子大小为 $a_i$，给 $m$ 个朋友戴前 $i$ 顶帽子（**必须用完**），小帽子在上大帽子在下，即需要满足**严格递减**。有的朋友**可以不戴帽子**。求有几种方案。
## 思路
对于一顶大小为 $a_i$ 的帽子，由于相同大小的帽子不能在同一个人头上，所以想要用掉需要一个新的朋友，即头上没有大小为 $a_i$ 的帽子的人。
对于第 $k$ 次出现的大小为 $a_i$ 的帽子，可选的人数为 $m - k + 1$ 个人。
方案数为前 $i - 1$ 顶帽子的方案数乘上第 $i$ 顶帽子能戴的人数。（**别忘了模 $998244353$ 喵！**）
## 代码
```cpp
/*
给个关注吧（会有粉福哒），球球啦 QwQ
给个赞吧喵 TAT
*/
#include<bits/stdc++.h>
using namespace std;
using ll = long long ;
const int N = 4e5 + 10, MOD = 998244353;
ll t, n, m, a[N], c[N], ans;
void solve() {
ans = 1; //初始化，好习惯喵
cin >> n >> m;
for (int i = 1; i <= n; ++i)
c[i] = 0; //我也是喵 =v=
for (int i = 1; i <= n; ++i) {
cin >> a[i];
if (c[a[i]] >= m) ans = 0;
//如果此时有一个尺寸的数量超过总人数，则无法满足全用完的条件，故方案数为 0
else
ans = ans * (m - c[a[i]]) % MOD;
c[a[i]]++;
cout << ans << ' ';
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> t;
while (t--)
solve();
return 0;
}
```