合界科技网站建设,网站功能设计,友汇网站建设管理后台,网站项目设计具体方案2021牛客OI赛前集训营-提高组#xff08;第三场#xff09;
题目大意
有2n2^n2n个选手参加拳击比赛#xff0c;每个人都有一个实力#xff0c;所有选手的实力用一个111到2n2^n2n的排列表示。
淘汰赛的规则是#xff1a;每次相邻的两个选手进行比赛#xff0c;实力值大…2021牛客OI赛前集训营-提高组第三场
题目大意
有2n2^n2n个选手参加拳击比赛每个人都有一个实力所有选手的实力用一个111到2n2^n2n的排列表示。
淘汰赛的规则是每次相邻的两个选手进行比赛实力值大的晋级到下一轮。
你的实力为111。为了取胜你买通了mmm个选手使得你与他们比赛时让你获胜。你想要获得冠军且你战胜的选手的实力值构成的序列的最长上升子序列长度要≥k\geq k≥k。求满足条件的方案数。 题解
我们先考虑k1k1k1的情况。
在这种情况下我们只需要让叶子节点111到根节点的路径上所有的点都被已经收买的人占了且满足这些点都是其子树的最大值。
将被收买的人按实力值从小到大排序。设fi,jf_{i,j}fi,j表示已经处理了前iii个被收买的人jjj的二进制的每一位表示这个位置上是否有被收买的人占据。那么转移式如下
fi,j2kfi,j×Cai−j−22k−1×(2k)!f_{i,j2^k}f_{i,j}\times C_{a_i-j-2}^{2^k-1}\times (2^k)!fi,j2kfi,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
#includebits/stdc.h
using namespace std;
int n,m,k,a[25];
long long ans,yh[1005][1005],jc[1005],f[25][115];
long long mod;
long long mi(long long t,long long v){if(!v) return 1;long long remi(t,v/2);rere*re%mod;if(v1) rere*t%mod;return re;
}
void init(){yh[0][0]1;for(int i1;i1000;i){yh[i][0]yh[i][i]1;for(int j1;ji;j) yh[i][j](yh[i-1][j-1]yh[i-1][j])%mod;}jc[0]1;for(int i1;i1000;i) jc[i]jc[i-1]*i%mod;
}
int main()
{scanf(%d%d%d%lld,n,m,k,mod);for(int i1;im;i){scanf(%d,a[i]);}sort(a1,am1);init();f[0][0]1;for(int i1;im;i){for(int j0;j(1n);j){if(f[i-1][j]){f[i][j](f[i][j]f[i-1][j])%mod;for(int t0;tn;t){if(((jt)1)0a[i]j(1t)1){f[i][j(1t)](f[i][j(1t)]f[i-1][j]*yh[a[i]-j-2][(1t)-1]%mod*jc[1t]%mod)%mod;}}}}}ansf[m][(1n)-1]*mi(2,n)%mod;printf(%lld,ans);return 0;
}再来考虑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的状态。状态的数量并不大n9n9n9的时候才不到120000120000120000。用这些状态来当之前状压的状态这样即可求出答案。
时间复杂度为O(120000nm)O(120000nm)O(120000nm)。
code
#includebits/stdc.h
#define N 120000
using namespace std;
int n,m,k,tot0,t10,a[25],cnt[N5];
long long ans0,yh[1005][1005],jc[1005],f[25][N5];
long long mod;
string pt[N5],to[N5];
mapstring,intz,re;
void dfs(string s,int now){if(!z[s]){z[s]1;pt[tot]s;}else return;if(nown) return;char c0;for(int i0;in;i){if(s[i]0){s[i]c1;dfs(s,now1);s[i]0;}else cmax(c,s[i]);}
// for(int i0;in;i){
// if(s[i]0){
// string ts;
// char c0;
// for(int j0;ji;j){
// cmax(c,s[j]);
// }
// t[i]c1;
// dfs(t,now1);
// }
// }
}
void dd(){for(int i1;itot;i){string spt[i];char c0;for(int j0;jn;j){if(s[j]0){s[j]c1;c;}else cmax(c,s[j]);}
// c0;
// for(int j0;jn;j) cmax(c,s[j]);if(c0k){to[t1]pt[i];re[pt[i]]t1;}}for(int i1;it1;i){for(int j0;jn;j){if(to[i][j]!0) cnt[i]|(1j);}}
}
void init(){yh[0][0]1;for(int i1;i1000;i){yh[i][0]yh[i][i]1;for(int j1;ji;j) yh[i][j](yh[i-1][j-1]yh[i-1][j])%mod;}jc[0]1;for(int i1;i1000;i) jc[i]jc[i-1]*i%mod;
}
long long mi(long long t,long long v){if(!v) return 1;long long remi(t,v/2);rere*re%mod;if(v1) rere*t%mod;return re;
}
void gt(string s,int t){char c0;for(int i0;it;i) cmax(c,s[i]);s[t]c1;
}
int main()
{scanf(%d%d%d%lld,n,m,k,mod);for(int i1;im;i){scanf(%d,a[i]);}sort(a1,am1);string s;for(int i1;in;i) ss0;dfs(s,0);dd();init();f[0][1]1;for(int i1;im;i){for(int j1;jt1;j){if(f[i-1][j]){f[i][j](f[i][j]f[i-1][j])%mod;string nowto[j],nxt;for(int t0;tn;t){if(now[t]0a[i]cnt[j](1t)1){nxtnow;gt(nxt,t);f[i][re[nxt]](f[i][re[nxt]]f[i-1][j]*yh[a[i]-cnt[j]-2][(1t)-1]%mod*jc[1t]%mod)%mod;}}}}}for(int i1;it1;i){if(cnt[i](1n)-1){ans(ansf[m][i])%mod;}}ansans*mi(2,n)%mod;printf(%lld,ans);return 0;
}
