P14364

lsj2009 · 2025-11-01 21:51:21 · 题解

贡献延后计算。什么意思？分析一下这个过程，设未被招聘上的人数为 cnt，若当前 s_i=0 大家都一样，否则 s_i=1 则 c_i\le cnt 都一样；而且 cnt 是不降的。如此，我们在 dp 的时候将所有数划分为 \le cnt 和 > cnt 的两集合 (S_0,S_1)，当 cnt 增加时考察哪些数从 S_1\to S_0，在这时计算这些数带来的贡献。具体的：

记 f_{i,j,k} 表示考虑了 p_{1\sim i}，有 j 个没招聘上，其中有 k 个的 c>j。在 j\to j+1 的时候考察 k 当中有多少个是 c=j+1 的。具体的，以下给出转移：（记 a_i=\sum\limits_{1\le j\le n}[c_j=i],b_i=\sum\limits_{1\le j\le i} a_j）

• 若 s_i=0：则此时无论如何都未招聘上，j 必然加一，则考察 c_{p_i} 和 j+1 的大小：
  • 若 c_{p_i}\le j+1：枚举 c_{p_{q< i}}=j+1 的个数 t， f_{i-1,j,k}\binom{a_{j+1}}{t}\binom{k}{t}t!(b_{j+1}-((i-1)-(k-t)))\to f_{i,j+1,k-t}
  • 若 c_{p_i}>j+1：枚举 c_{p_{q<i}}=j+1 的个数 t， f_{i-1,j,k}\binom{a_{j+1}}{t}\binom{k}{t}t!\to f_{i,j+1,k-t+1}
• 若 s_i=1：
  • 若 c_{p_i}\le j：则未被招聘上，j 加一，枚举 c_{p_{q<i}}=j+1 的个数 t， f_{i-1,j,k}\binom{a_{j+1}}{t}\binom{k}{t}t!(b_j-((i-1)-k))\to f_{i,j+1,k-t}
  • 若 c_{p_i}>j：则被招聘上， f_{i-1,j,k}\to f_{i,j,k+1}

由于 t\le a_i 而 \sum a_i=n，故上述做法暴力 dp 即为 \mathcal{O}(n^3)。

#include<bits/stdc++.h>
// #define int long long
// #pragma GCC optimize(3,"Ofast","inline")
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ll long long
#define bint __int128
#define ull unsigned long long
#define uint unsigned int
#define ld double
#define PII pair<int,int>
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define umap unordered_map
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
#define pcnt(x) __builtin_popcount(x)
#define lg(x) (31-__builtin_clz(x))
using namespace std;
void file_IO() {
    freopen("employ.in","r",stdin);
    freopen("employ.out","w",stdout);
}
bool M1;
const int INF=0x3f3f3f3f;
const ll INFLL=0x3f3f3f3f3f3f3f3f;
const ld eps=1e-9;
struct mint {
 ...
};
const int N=5e2+5;
mint jc[N],inv_jc[N];
void init(int n=5e2) {
    jc[0]=1;
    rep(i,1,n)
        jc[i]=jc[i-1]*i;
    inv_jc[n]=~jc[n];
    per(i,n-1,0)
        inv_jc[i]=inv_jc[i+1]*(i+1);
}
mint C(int n,int m) {
    if(m<0||n<m)
        return 0;
    return jc[n]*inv_jc[n-m]*inv_jc[m];
}
mint P(int n,int m) {
    if(m<0||n<m)
        return 0;
    return jc[n]*inv_jc[n-m];
}
int c[N],pre[N];
mint f[N][N][N];
char s[N];
void solve() {
    int n,m;
    scanf("%d%d",&n,&m);
    scanf("%s",s+1);
    rep(i,1,n) {
        int x;
        scanf("%d",&x);
        ++c[x];
    }
    pre[0]=c[0];
    rep(i,1,n)
        pre[i]=pre[i-1]+c[i];
    f[0][0][0]=1;
    rep(i,1,n) {
        rep(j,0,i-1) {
            rep(k,0,i-1) {
                if(s[i]==48) {
                    rep(t,0,min(k,c[j+1])) {
                        if(pre[j+1]>=(i-1)-(k-t))
                            f[i][j+1][k-t]+=f[i-1][j][k]*C(c[j+1],t)*P(k,t)*(pre[j+1]-((i-1)-(k-t)));
                        f[i][j+1][k-t+1]+=f[i-1][j][k]*C(c[j+1],t)*P(k,t);
                    }
                } else {
                    rep(t,0,min(k,c[j+1])) {
                        if(pre[j+1]>=(i-1)-k)
                            f[i][j+1][k-t]+=f[i-1][j][k]*C(c[j+1],t)*P(k,t)*(pre[j]-((i-1)-k));
                    }
                    f[i][j][k+1]+=f[i-1][j][k];
                }
            }
        }
    }
    mint res=0;
    rep(j,0,n-m)
        res+=f[n][j][n-pre[j]]*jc[n-pre[j]];
    printf("%d\n",res.x);
}
bool M2;
// g++ employ.cpp -std=c++14 -Wall -O2 -o employ
signed main() {
    file_IO();
    int testcase=1;
    init();
    // scanf("%d",&testcase);
    while(testcase--)
        solve();
    debug("used time = %dms\n",(signed)(1000*clock()/CLOCKS_PER_SEC));
    debug("used memory = %dMB\n",(signed)((&M1-&M2)/1024/1024));
    return 0;
}