2021牛客OI赛前集训营-提高组（第三场） T3打拳

2021牛客OI赛前集训营-提高组（第三场）

题目大意

有$2^n$个选手参加拳击比赛，每个人都有一个实力，所有选手的实力用一个$1$到$2^n$的排列表示。

淘汰赛的规则是：每次相邻的两个选手进行比赛，实力值大的晋级到下一轮。

你的实力为$1$。为了取胜，你买通了$m$个选手，使得你与他们比赛时让你获胜。你想要获得冠军，且你战胜的选手的实力值构成的序列的最长上升子序列长度要$\ge k$。求满足条件的方案数。

题解

我们先考虑$k=1$的情况。

在这种情况下，我们只需要让叶子节点$1$到根节点的路径上所有的点都被已经收买的人占了，且满足这些点都是其子树的最大值。

将被收买的人按实力值从小到大排序。设$f_{i,j}$表示已经处理了前$i$个被收买的人，$j$的二进制的每一位表示这个位置上是否有被收买的人占据。那么转移式如下

$f_{i,j+2^k}+=f_{i,j}\times C_{a_i-j-2}^{2^k-1}\times (2^k)!$，其中$k$为$j$的二进制位中为$0$的位。

$C_{a_i-j-2}^{2^k-1}$表示在实力在比$a_i$小的没有选过且不为$1$的$a_i-j-2$个选手中选$2^k-1$（因为已经确定了要有$a_i$，所以 要减1）个来组成$k$位置的子树。

因为子树内部可以任意排序，所以要乘上$(2^k)!$。

输出答案时，因为$1$的位置任意，所以要乘上$2^n$。

时间复杂度为$O(2^{n}nm)$。

code

#include<bits/stdc++.h>
using namespace std;
int n,m,k,a[25];
long long ans,yh[1005][1005],jc[1005],f[25][1<<15];
long long mod;
long long mi(long long t,long long v){if(!v) return 1;long long re=mi(t,v/2);re=re*re%mod;if(v&1) re=re*t%mod;return re;
}
void init(){yh[0][0]=1;for(int i=1;i<=1000;i++){yh[i][0]=yh[i][i]=1;for(int j=1;j<i;j++) yh[i][j]=(yh[i-1][j-1]+yh[i-1][j])%mod;}jc[0]=1;for(int i=1;i<=1000;i++) jc[i]=jc[i-1]*i%mod;
}
int main()
{scanf("%d%d%d%lld",&n,&m,&k,&mod);for(int i=1;i<=m;i++){scanf("%d",&a[i]);}sort(a+1,a+m+1);init();f[0][0]=1;for(int i=1;i<=m;i++){for(int j=0;j<(1<<n);j++){if(f[i-1][j]){f[i][j]=(f[i][j]+f[i-1][j])%mod;for(int t=0;t<n;t++){if(((j>>t)&1)==0&&a[i]>=j+(1<<t)+1){f[i][j+(1<<t)]=(f[i][j+(1<<t)]+f[i-1][j]*yh[a[i]-j-2][(1<<t)-1]%mod*jc[1<<t]%mod)%mod;}}}}}ans=f[m][(1<<n)-1]*mi(2,n)%mod;printf("%lld",ans);return 0;
}

再来考虑$k\ge 1$的情况。

我们可以考虑对LIS（最长上升子序列）的维护方法。

从小到大依次来维护每个数字的LIS，这个数字的LIS等于在其之前的所有数字的LIS的最大值+1。

比如四个数字{3,1,2,4}\{3,1,2,4\}{3,1,2,4}，每次操作如下

{0,1,0,0}\{0,1,0,0\}{0,1,0,0}

{0,1,2,0}\{0,1,2,0\}{0,1,2,0}

{1,1,2,0}\{1,1,2,0\}{1,1,2,0}

{1,1,2,3}\{1,1,2,3\}{1,1,2,3}

我们可以暴力求出所有经过LIS过程后最大的LIS值能够$\ge k$的状态。状态的数量并不大，$n=9$的时候才不到$120000$。用这些状态来当之前状压的状态，这样即可求出答案。

时间复杂度为$O(120000nm)$。

code

#include<bits/stdc++.h>
#define N 120000
using namespace std;
int n,m,k,tot=0,t1=0,a[25],cnt[N+5];
long long ans=0,yh[1005][1005],jc[1005],f[25][N+5];
long long mod;
string pt[N+5],to[N+5];
map<string,int>z,re;
void dfs(string s,int now){if(!z[s]){z[s]=1;pt[++tot]=s;}else return;if(now==n) return;char c='0';for(int i=0;i<n;i++){if(s[i]=='0'){s[i]=c+1;dfs(s,now+1);s[i]='0';}else c=max(c,s[i]);}
//	for(int i=0;i<n;i++){
//		if(s[i]=='0'){
//			string t=s;
//			char c='0';
//			for(int j=0;j<i;j++){
//				c=max(c,s[j]);
//			}
//			t[i]=c+1;
//			dfs(t,now+1);
//		}
//	}
}
void dd(){for(int i=1;i<=tot;i++){string s=pt[i];char c='0';for(int j=0;j<n;j++){if(s[j]=='0'){s[j]=c+1;c++;}else c=max(c,s[j]);}
//		c='0';
//		for(int j=0;j<n;j++) c=max(c,s[j]);if(c>='0'+k){to[++t1]=pt[i];re[pt[i]]=t1;}}for(int i=1;i<=t1;i++){for(int j=0;j<n;j++){if(to[i][j]!='0') cnt[i]|=(1<<j);}}
}
void init(){yh[0][0]=1;for(int i=1;i<=1000;i++){yh[i][0]=yh[i][i]=1;for(int j=1;j<i;j++) yh[i][j]=(yh[i-1][j-1]+yh[i-1][j])%mod;}jc[0]=1;for(int i=1;i<=1000;i++) jc[i]=jc[i-1]*i%mod;
}
long long mi(long long t,long long v){if(!v) return 1;long long re=mi(t,v/2);re=re*re%mod;if(v&1) re=re*t%mod;return re;
}
void gt(string &s,int t){char c='0';for(int i=0;i<t;i++) c=max(c,s[i]);s[t]=c+1;
}
int main()
{scanf("%d%d%d%lld",&n,&m,&k,&mod);for(int i=1;i<=m;i++){scanf("%d",&a[i]);}sort(a+1,a+m+1);string s;for(int i=1;i<=n;i++) s=s+'0';dfs(s,0);dd();init();f[0][1]=1;for(int i=1;i<=m;i++){for(int j=1;j<=t1;j++){if(f[i-1][j]){f[i][j]=(f[i][j]+f[i-1][j])%mod;string now=to[j],nxt;for(int t=0;t<n;t++){if(now[t]=='0'&&a[i]>=cnt[j]+(1<<t)+1){nxt=now;gt(nxt,t);f[i][re[nxt]]=(f[i][re[nxt]]+f[i-1][j]*yh[a[i]-cnt[j]-2][(1<<t)-1]%mod*jc[1<<t]%mod)%mod;}}}}}for(int i=1;i<=t1;i++){if(cnt[i]==(1<<n)-1){ans=(ans+f[m][i])%mod;}}ans=ans*mi(2,n)%mod;printf("%lld",ans);return 0;
}