2021牛客OI赛前集训营-提高组（第三场） T3打拳
2021牛客OI赛前集训营-提高组（第三场）
题目大意
有2n2^n2n个选手参加拳击比赛，每个人都有一个实力，所有选手的实力用一个111到2n2^n2n的排列表示。
淘汰赛的规则是：每次相邻的两个选手进行比赛，实力值大的晋级到下一轮。
你的实力为111。为了取胜，你买通了mmm个选手，使得你与他们比赛时让你获胜。你想要获得冠军，且你战胜的选手的实力值构成的序列的最长上升子序列长度要≥k\geq k≥k。求满足条件的方案数。
题解
我们先考虑k=1k=1k=1的情况。
在这种情况下，我们只需要让叶子节点111到根节点的路径上所有的点都被已经收买的人占了，且满足这些点都是其子树的最大值。
将被收买的人按实力值从小到大排序。设fi,jf_{i,j}fi,j表示已经处理了前iii个被收买的人，jjj的二进制的每一位表示这个位置上是否有被收买的人占据。那么转移式如下
fi,j+2k+=fi,j×Cai−j−22k−1×(2k)!f_{i,j+2^k}+=f_{i,j}\times C_{a_i-j-2}^{2^k-1}\times (2^k)!fi,j+2k+=fi,j×Cai−j−22k−1×(2k)!，其中kkk为jjj的二进制位中为000的位。
Cai−j−22k−1C_{a_i-j-2}^{2^k-1}Cai−j−22k−1表示在实力在比aia_iai小的没有选过且不为111的ai−j−2a_i-j-2ai−j−2个选手中选2k−12^k-12k−1（因为已经确定了要有aia_iai，所以 要减1）个来组成kkk位置的子树。
因为子树内部可以任意排序，所以要乘上(2k)!(2^k)!(2k)!。
输出答案时，因为111的位置任意，所以要乘上2n2^n2n。
时间复杂度为O(2nnm)O(2^nnm)O(2nnm)。
code
#include
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;jscanf("%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<if(f[i-1][j]){f[i][j]=(f[i][j]+f[i-1][j])%mod;for(int t=0;tif(((j>>t)&1)==0&&a[i]>=j+(1<f[i][j+(1< 再来考虑k≥1k\geq 1k≥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值能够≥k\geq k≥k的状态。状态的数量并不大，n=9n=9n=9的时候才不到120000120000120000。用这些状态来当之前状压的状态，这样即可求出答案。
时间复杂度为O(120000nm)O(120000nm)O(120000nm)。
code
#include
#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];
mapz,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;iif(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
// if(s[i]=='0'){
// string t=s;
// char c='0';
// for(int j=0;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;jif(s[j]=='0'){s[j]=c+1;c++;}else c=max(c,s[j]);}
// c='0';
// for(int j=0;j='0'+k){to[++t1]=pt[i];re[pt[i]]=t1;}}for(int i=1;i<=t1;i++){for(int j=0;jif(to[i][j]!='0') cnt[i]|=(1<yh[0][0]=1;for(int i=1;i<=1000;i++){yh[i][0]=yh[i][i]=1;for(int j=1;jif(!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;iscanf("%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;tif(now[t]=='0'&&a[i]>=cnt[j]+(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<if(cnt[i]==(1<ans=(ans+f[m][i])%mod;}}ans=ans*mi(2,n)%mod;printf("%lld",ans);return 0;
}