P14364

贡献延后计算。什么意思？分析一下这个过程，设未被招聘上的人数为

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$ $s_{i} = 0$ ：则此时无论如何都未招聘上， $j$ $j$ 必然加一，则考察 $c_{p_i}$ $c_{p_{i}}$ 和 $j+1$ $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$ $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)

。

CPP

#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;
}

文章操作

相关推荐

评论

P14364