【题解】2021牛客OI赛前集训营-提高组（第三场）C. 打拳

【题解】2021牛客OI赛前集训营-提高组（第三场）C. 打拳

需要一些脑洞。

充分体现了本蒟蒻 dp 菜的本质。

考虑 k=1 的情况。这种情况等价于，从 叶子结点 1 到根节点的所有祖先都被收买，且满足祖先节点都是子树的最大值。

那么我们考虑设 dp[i][j] 表示处理了前 i 个被收买的人，其中 jin [0,2^n) 表示每个位置上的数是否被选择。转移时就找到一个不为 1 的位置，假设为 k，那么乘上一个组合数 ( b e a t [ i ] − c n t [ j ] − 2 2 k − 1 ) binom{beat[i]-cnt[j]-2}{2^k-1} (2k−1beat[i]−cnt[j]−2​) 以及 beat[i] 子树内部的顺序 ( 2 k ) ! (2^k)! (2k)! 。

最后我们要注意到其实 1的位置并没有固定 ，所以要乘上 2 n 2^{n} 2n 。

时间复杂度 o ( 2 n n m ) o(2^nnm) o(2nnm) ，期望得分 50pts 。（能做到这一步已经很优秀了 qwq）

代码量不大。但是很有效。

#include
#define ll long long
using namespace std;
const int N=120000;
//solution 65 pts ： 打拳
int mod;
int beat[N];
int n,m,k;
ll C[550][550];
ll fact[550];
void init2() {
	fact[0]=1;
	for(int i=1;i<=530;i++) fact[i]=fact[i-1]*i%mod;
	for(int i=0;i<=530;i++) C[i][0]=1;
	for(int i=1;i<=530;i++) {
		for(int j=1;j<=i;j++) {
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
		}
	}
	return;
}
void add(ll &x,ll y) {
	x=(x+y)%mod;
}
ll dp[17][N];
ll fpow(ll x,ll y) {
	ll mul(1);
	for(;y;y>>=1) {
		if(y&1) mul=mul*x%mod;
		x=x*x%mod; 
	}
	return mul;
}
void work() {
	dp[0][0]=1;
	for(int i=0;i>k)&1)==0)&&beat[i]>=(j+(1<n>>m>>k>>mod;
	for(int i=0;i>beat[i];
	sort(beat,beat+m);
	init2();
	work();
	return 0;
}

为了得到 100pts ，我们还需要对 LIS 进行转移 （其实这里思维难度不大，就是比较繁琐）

考虑怎么求一个序列的 LCS （我们重新定义求法）

从小到大考虑，每个位置的 LCS = i 前面 LCS 的最大值 + 1

这样我们考虑到序列长度还是 n ，总状态数只有区区 120000

所以时间复杂度为 o ( 120000 n m ) o(120000nm) o(120000nm) 可以通过。实际实现时要先写一个 dfs 把所有合法状态搜出来方便转移。

代码参见 std 。

#include
#define ll long long
using namespace std;
const int N=120000;
//solution 100 pts ： 打拳
int mod;
int beat[105];
string s;
map vis;
vector ans;
int tot=0;
int n,m,k;
void dfs(string s,int len) {
	if(vis[s]==0) {
		vis[s]=1;
		ans.push_back(s);
		tot++;
	}
	else return;
	if(len==n) return;
	for(int i=0;i ID;
int num=0;
ll cnt[N];
void init() {
	for(int i=0;i='0'+k) {
			S[++num]=ans[i];
			ID[ans[i]]=num;
		}
	}
	for(int i=1;i<=num;i++) {
		for(int j=0;j>=1) {
		if(y&1) mul=mul*x%mod;
		x=x*x%mod; 
	}
	return mul;
}
//核心代码这么短 ？？ 
void work() {
	dp[0][1]=1;
	for(int i=0;i=(cnt[j]+(1<n>>m>>k>>mod;
	for(int i=0;i>beat[i];
	sort(beat,beat+m);
	for(int i=1;i<=n;i++) s=s+'0';
	dfs(s,0);
	init();
	init2();
	work();
	return 0;
}