uoj#311 【UNR #2】积劳成疾

题目

考虑直接顺着从\(1\)填数填到\(n\)发现这是在胡扯

所以考虑一些奇诡的东西，譬如最后的答案长什么样子

显然某一种方案的贡献是一个\(\prod_{i=1}^nw_i^{t_i}\)状物，\(t_i\)表示\(i\)在多少个长度为\(m\)的区间里为最大值

而这里又是最大值，所以可以考虑从大到小填数，每次把填完之后相应的分裂区间，同时在这个时候也可以计算一些贡献

于是我们设\(f_{l,r,k}\)表示对于区间\([l,r]\)最大值为\(k\)，我们枚举这个最大值最后一次出现的位置，同时跨过这个位置长度为\(m\)的区间的最大值肯定是\(k\)了，于是我们在这里就可以计算出\(w_k\)的贡献

于是有

\[f_{l,r,k}=\sum_{i=l}^{r}w_k^{calc(r-l+1,i)}\sum_{j=1}^kf_{l,i-1,j}\times \sum_{j=1}^{k-1}f_{i+1,r,j}
\]

其中\(calc(r-l+1,i)\)表示对于一个长度为\(r-l+1\)的序列，有多少个长度为\(m\)的区间跨过\(i\)位置

发现这里能维护前缀和就能快速转移了

答案就是\(\sum_{i=1}^nf_{1,n,i}\)

同时我们发现这里维护区间太奢侈了，只要有一个区间长度我们就能转移了，所以我们直接改为维护区间长度

状态数\(n^2\)，转移复杂度\(O(n)\)，复杂度为\(O(n^3)\)

代码

#include<bits/stdc++.h>

#define re register

#define LL long long

const int mod=998244353;

const int maxn=403;

int n,m,w[maxn];

int dp[maxn][maxn],vis[maxn][maxn],a[maxn][maxn],b[maxn][maxn];

inline int ksm(int a,int b) {

	int S=1;

	for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) S=1ll*S*a%mod;

	return S;

}

int f(int l,int k) {

	if(!l) return 1;

	if(!k) return 0;

	if(vis[l][k]) return dp[l][k];

	if(l<m) {

		vis[l][k]=1;

		return dp[l][k]=ksm(k,l);

	}

	if(k>1) dp[l][k]=f(l,k-1);

	for(re int i=0;i<l;i++)

		dp[l][k]=(dp[l][k]+1ll*f(i,k)*f(l-i-1,k-1)%mod*a[k][b[l][i+1]]%mod)%mod;

	vis[l][k]=1;

	return dp[l][k];

}

int main() {

	scanf("%d%d",&n,&m);

	for(re int i=1;i<=n;i++) a[i][0]=1;

	for(re int i=1;i<=n;i++) scanf("%d",&a[i][1]),w[i]=a[i][1];

	for(re int i=1;i<=n;i++)

		for(re int j=1;j+m-1<=i;j++)

			for(re int k=j;k<=j+m-1;k++)

				b[i][k]++;

	for(re int i=1;i<=n;i++)

		for(re int j=2;j<=n;j++)

			a[i][j]=1ll*a[i][j-1]*w[i]%mod;

	printf("%d\n",f(n,n));

	return 0;

}

巴特西

uoj#311 【UNR #2】积劳成疾

最新文章

热门文章