记录编号	609426	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	4199.[CSP-S 2025 T4]员工招聘	最终得分	100
用户昵称	金牌教师王艳芳	是否通过	通过
代码语言	C++	运行时间	4.938 s
提交时间	2025-11-09 18:08:48	内存使用	6.10 MiB

#include <bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,m,s[505],c[505],cnt[505],pre[505],C[505][505],jc[505],pl[505][505],dp[2][505][505];

int main(){
    freopen("employ.in","r",stdin);
    freopen("employ.out","w",stdout);
    string str;
    cin>>n>>m>>str;
    for(int i=0;i<n;i++)s[i]=str[i]-'0';
    for(int i=1;i<=n;i++)cin>>c[i];
    
    sort(c+1,c+n+1);
    
    for(int i=1;i<=n;i++)cnt[c[i]]++;
    
    pre[0]=cnt[0];
    for(int i=1;i<=n;i++)pre[i]=pre[i-1]+cnt[i];
    
    for(int i=0;i<=n;i++){
        C[i][0]=C[i][i]=1;
        for(int j=1;j<i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }
    
    jc[0]=1;
    for(int i=1;i<=n;i++)jc[i]=(long long)jc[i-1]*i%mod;
    
    for(int i=0;i<=n;i++){
        pl[i][0]=1;
        for(int j=1;j<=i;j++)pl[i][j]=(long long)pl[i][j-1]*(i-j+1)%mod;
    }
    
    dp[0][0][0]=1;
    int cur=0;
    
    for(int i=0;i<n;i++){
        int nxt=1-cur;
        for(int j=0;j<=n;j++)for(int k=0;k<=n;k++)dp[nxt][j][k]=0;
        
        for(int j=0;j<=i;j++){
            for(int k=0;k<=i;k++){
                if(!dp[cur][j][k])continue;
                
                if(s[i]==1){
                    dp[nxt][j][k+1]=(dp[nxt][j][k+1]+dp[cur][j][k])%mod;
                    
                    if(pre[j]>=i-k){
                        int left=pre[j]-(i-k);
                        if(left>0){
                            int maxt=k;
                            if(maxt>cnt[j+1])maxt=cnt[j+1];
                            for(int t=0;t<=maxt;t++){
                                int zs=C[cnt[j+1]][t];
                                int px=pl[k][t];
                                long long add=(long long)dp[cur][j][k]*left%mod*zs%mod*px%mod;
                                dp[nxt][j+1][k-t]=(dp[nxt][j+1][k-t]+add)%mod;
                            }
                        }
                    }
                }else{
                    int maxt=k;
                    if(maxt>cnt[j+1])maxt=cnt[j+1];
                    for(int t=0;t<=maxt;t++){
                        int zs=C[cnt[j+1]][t];
                        int px=pl[k][t];
                        
                        if(pre[j+1]>=i-k+t){
                            int left=pre[j+1]-(i-k+t);
                            if(left>0){
                                long long add=(long long)dp[cur][j][k]*left%mod*zs%mod*px%mod;
                                dp[nxt][j+1][k-t]=(dp[nxt][j+1][k-t]+add)%mod;
                            }
                        }
                        
                        long long add=(long long)dp[cur][j][k]*zs%mod*px%mod;
                        dp[nxt][j+1][k-t+1]=(dp[nxt][j+1][k-t+1]+add)%mod;
                    }
                }
            }
        }
        
        cur=nxt;
    }
    
    long long ans=0;
    for(int j=0;j<=n-m;j++){
        int k=n-pre[j];
        ans=(ans+(long long)dp[cur][j][k]*jc[k])%mod;
    }
    
    cout<<ans<<endl;
    return 0;
}