• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

AT3962 [AGC024E] Sequence Growing Hard 题解

开发技术 开发技术 4小时前 2次浏览

Link.

ATcoder
Luogu

Desc++ription.

给定 (n,k,m),统计序列序列数 ({A_i(iin[0,n])}),使得

  • (text{size}(A_i)=i)
  • (forall iin[1,n],jin[1,i],A_i(j)in[1,k])
  • (forall iin[1,n])(A_{i-1})(A_i) 的子序列且字典序小于 (A_i)

Solution.

自己的想法:
题意转化成了求不同操作序列数

  1. 每次末尾插入一个任意元素
  2. 每次在第 (k) 个位置插入一个权值 (>a_k) 的元素

题解:
发现在开头插个 (0),上面的 (1) 就和 (2) 合并了,两者是本质相同的。
然后考虑建树,一个点向它插入位置连边,还要记录一个当前是第几次操作。
本质上来说,一个点当前第几次操作其实在树的形态确定时是基本确定的。
只能在所有儿子改变顺序时才能变。

那我们考虑记录 (dp_{x,y}) 表示大小为 (x) 根权为 (y) 的子树的方案数。
我们枚举第一个子树是什么,然后删掉后 (dp) 状态是已知的。
枚举第一个子树的大小和根权,则有

[begin{aligned}
dp_{x,y}&=sum_{a=1}^{x-1}sum_{v=y+1}^kdbinom{x-2}{a-1}cdot dp_{x-a,y}cdot dp_{a,v}\
&=sum_{a=1}^{x-1}dbinom{x-2}{a-1}cdot dp_{x-a,y}cdot sum_{v=y+1}^k dp_{a,v}
end{aligned}
]

Coding.

点击查看代码
//是啊,你就是那只鬼了,所以被你碰到以后,就轮到我变成鬼了{{{
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
	x=0;char c=getchar(),f=0;
	for(;c<48||c>57;c=getchar()) if(!(c^45)) f=1;
	for(;c>=48&&c<=57;c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	f?x=-x:x;
}
template<typename T,typename...L>inline void read(T &x,L&...l) {read(x),read(l...);}//}}}
int n,K,P,dp[305][305],sm[305][305],C[305][305];
inline void upd(int &a,int b) {(a+=b)>=P?a-=P:a;}
int main()
{
	read(n,K,P);for(int i=K;i>=0;i--) sm[1][i]=sm[1][i+1]+(dp[1][i]=1);
	for(int i=0;i<=n;i++) {C[i][0]=1;for(int j=1;j<=i;j++) upd(C[i][j]=C[i-1][j-1],C[i-1][j]);}
	for(int i=2;i<=n+1;i++) for(int j=K;j>=0;upd(sm[i][j]=sm[i][j+1],dp[i][j]),j--)
		for(int l=1;l<i;l++) upd(dp[i][j],1ll*C[i-2][l-1]*dp[i-l][j]%P*sm[l][j+1]%P);
	return printf("%dn",dp[n+1][0]),0;
}

程序员灯塔
转载请注明原文链接:AT3962 [AGC024E] Sequence Growing Hard 题解
喜欢 (0)