他钦定自己能进省队。
你钦定这个人能选上。
我钦定我就是个废物。
我们都有光明的未来。
\(n\) 个人来面试，你可以任意安排面试顺序。
第 \(i\) 天的面试难度为 \(s_i\)。\(s_i=0\) 表示第 \(i\) 天的面试难度过高，没有人能够通过。\(s_i=1\) 表示第 \(i\) 天的面试难度过低，所有人都能通过。
第 \(i\) 个人有一个耐心值 \(c_i\)，若在他面试前有至少 \(c_i\) 个人未通过面试或放弃面试，则他会放弃面试。
求至少 \(m\) 人通过面试的方案数，对 \(998244353\) 取模。
\(1 \leq m \leq n \leq 500\)，\(0 \leq c_i \leq n\)。
洛谷题解大学习，jiangly 大学习，钦定大学习，大学习大学习。
我们先钦定每天的人是否录取，设 \(x_i\) 表示前 \(i\) 天未录取的总人数，容易发现 \(x\) 是不降的。
-
对于 \(s_i=0\)，当天一定不会录取，任选一人放上去即可。
-
对于 \(s_i=1\)，进行分讨。
-
如果这一天需要录取，则当天的人需要满足 \(c > x_{i-1}\)。
-
如果这一天不需要录取，则当天的人需要满足 \(c \leq x_{i-1}\)。
-
考虑容斥。我们将 \(c_j > x_{i-1}\) 拆成任选一人后除去 \(c_j \leq x_{i-1}\) 的情况，这样就变得方便了。
钦定有什么好处？问题中，对于未钦定的人是可以人选的，所以我们只在钦定时区分所有人。
假设最后钦定了 \(k\) 人，则剩下 \(n-k\) 人的排列顺序可以随便选，将答案乘以 \((n-k)!\) 即可。
事实上，我们只关心这 \(k\) 人的位置及顺序，别的人我们最后处理。
接下来我们考虑 dp。设 \(d_{i,j,k}\) 表示前 \(i\) 天有 \(j\) 人未录取，且你钦定了 \(k\) 人，总共的方案数。
这里的 \(j\) 就是上面的 \(x_i\) 对吧。
我们考虑 \(d_{i,j,k}\) 能够转移到哪里。
-
对于 \(s_{i+1}=0\)，这里不需要区分人，\(d_{i+1,j+1,k} \leftarrow d_{i+1,j+1,k} + d_{i,j,k}\)。
-
对于 \(s_{i+1}=1\)，分讨。
-
假设第 \(i+1\) 天需要录取，进行容斥。
-
考虑任选一个人，则 \(d_{i+1,j,k} \leftarrow d_{i+1,j,k} + d_{i,j,k}\)。
-
接下来考虑钦定一个 \(c \leq j\) 的人，则 \(d_{i+1,j,k+1} \leftarrow d_{i+1,j,k+1} - T \times d_{i,j,k}\)。
-
-
假设第 \(i+1\) 天不需要录取，钦定一个 \(c \leq j\) 的人，则 \(d_{i+1,j+1,k+1} \leftarrow d_{i+1,j+1,k+1} + T \times d_{i,j,k}\)。
-
你注意到上文有一个神秘数字 \(T\) 还没有说明。是这样的，\(T\) 表示当前还能选出多少个 \(c_j \leq x_i\) 的人。
你考虑如果我们不使用这个 trick，我们并不能知道当前还有哪些人能选。
但是钦定了就不一样。考虑 \(x\) 是单调不降的，这意味着在你的状态里 \(j\) 也是单调不降的。
然后你就会发现你前面钦定的所有人一定会占用后面的名额。
假设 \(a_x\) 表示满足 \(c \leq x\) 的人数，则 \(T=a_j-k\) 对吧。
最后答案就是 \(\sum\limits_{j=0}^{n-m}\sum\limits_{k} d_{n,j,k} \times (n-k)!\)。
然后你发现做完了，操。
#include<iostream>
#include<cstdio>
using namespace std;
const int mod=998244353;
int a[510],fact[510],d[510][510][510];
char ch[510];
int main(){int n,m;scanf("%d %d",&n,&m);fact[0]=1;for(int i=1;i<=n;i++){cin>>ch[i];fact[i]=(long long)fact[i-1]*i%mod;}for(int i=1;i<=n;i++){int c;scanf("%d",&c);a[c]++;}for(int i=1;i<=n;i++){a[i]+=a[i-1];}d[0][0][0]=1;for(int i=0;i<n;i++){for(int j=0;j<=i;j++){for(int k=0;k<=i;k++){if(ch[i+1]=='0'){d[i+1][j+1][k]+=d[i][j][k];d[i+1][j+1][k]=(d[i+1][j+1][k]%mod+mod)%mod;}else{d[i+1][j][k]+=d[i][j][k];d[i+1][j][k]=(d[i+1][j][k]%mod+mod)%mod;int T=a[j]-k;d[i+1][j][k+1]-=(long long)T*d[i][j][k]%mod; d[i+1][j][k+1]=(d[i+1][j][k+1]%mod+mod)%mod;d[i+1][j+1][k+1]+=(long long)T*d[i][j][k]%mod; d[i+1][j+1][k+1]=(d[i+1][j+1][k+1]%mod+mod)%mod;}}}}int ans=0;for(int j=0;j<=n-m;j++){for(int k=0;k<=n;k++){ans+=(long long)d[n][j][k]*fact[n-k]%mod;ans=(ans%mod+mod)%mod;}}printf("%d",ans);return 0;
}
知道这个东西之后这一题有什么难点吗。
哦好吧我不知道而且我这一年惨败。
甚至在对着题解的情况下这道题也过了几个月才补掉。
哦我是废物啊那没关系了。
好吧说点今年打 OI 的感想吧。
从上半年打完省选之后就是一段低谷，或许也是在给我以前考试的 rp 背锅。
CSP-S 初赛考的貌似还好，然而到了复赛就惨败了。
T1 当时看了不知所云，做了一个半小时，赛后发现是黄题自闭了。
接下来在 T2 和 T3 来回横跳最后选择先写 T3 再写 T2。
过了前三题大样例之后打 T4 暴力，然后比赛结束了。
出考场以为自己这把还行，结果接下来就看到一堆言论。
比如说 T2 复杂度说是 \(O(2^k n)\) 才能过然而我写的是一个不知所云的东西。
我也不知道多了几个 \(k\) 但是他就是很悬，虽然最后过了就是。
比如说 T1 都是一堆反悔贪心只有我写了一个奇怪的一次调整做法。
虽然最后这个做法好像能过但是我并不知道他对不对。
比如说 T3，赛后在 LA 群看到一堆 Hash 配 Trie 或者是 AC 自动机的做法。
然而我是在 Trie 上暴力的，场上认为自己这个复杂度很对，毕竟大样例都跑过了。
然而我这样暴力的复杂度是和答案相关的，于是我 T 了。
然后 T4，本来以为自己拿到状压就是极限了。
结果最后发现只要再多一个输出 \(0\) 就能多拿 \(4\) 分。
倒闭了，然而你还有 NOIP 要打。
中途打了若干比赛，状态都不是特别理想。
然后就 NOIP 了，本来以为自己能够考好。
结果遇到今年的题目，真的彻底倒闭了。
平时考的比我差的这次比我好，平时比我好的早就甩我一两百分了。
你发现今年的 NOIP 是这样的，平时水平不高喜欢打暴力的这次看到题目难直接去拼好分了，平时水平很高的早就过穿了。
只有我这种又菜又爱玩的在那冲一整场 T2 然后不知所云最后暴力都没拿的。
也许今年就该在这里结束了吧。
接下来迎来了这一年最后一场比赛，THUPC 初赛。
本来都不指望参加的，结果赛前一天晚上家长给随机匹配到队友了。
第二天混了个 rk600，感觉挺有教育意义的一个名次。
然而不知道查重之后能拿多少名，所以挺难受的。
大概是什么感觉呢，你是班里的倒数第一，别人都注意到你了。
然后突然就转来几个混混抢了你的倒数第一，然后没人记住你了。
总之就是，今年输完了。
明年再战。