Description

\(n\in[1,500],k\in[2,10]\)。

Solution

这是一道有点很有难度的题。

先考虑判断一个数是否在数列\(a\)中。由于每次加的数是在\([0,k)\)的范围内，所以个位不定，但除个以外的位可以任意取值。
考虑DP。记个位为第\(1\)位，设\(g_{i,p,x,a}\)表示我们构造的数第\(2\sim i\)位为0，第\(i\sim\infty\)位中最大的位值为\(p\)，个位为\(a\)，此时我们要将第\(i\)位刚好填到\(x\)，个位变成了多少。
初值的话，可以暴力算出\(i\in[1,2]\)时的\(g\)。
不进位的转移显然。进位时，比如我们想算\(g_{i+1,p,1,a}\)的值，它可以由\(g_{i,k-1,1,a'}\)转移而来（\(a'\)表示我们在第\(i\)位填\(k-1\)次\(1\)后\(a\)会变成的数）。

然后做树形DP。如果我们沿着子树节点序列转移，那么实际上就是沿着dfs序转移，可以转移到\(dfn[i]\)的范围是\([dfn[fa[i]],dfn[i])\)。
设\(dp_{dfn[x],j,p,a}\)表示我们做到点\(x\)，考虑到第\(j\)位（第\(j\)位放\(d[x]\)），前面的位的最大值为\(p\)，个位为\(a\)的合法方案数。初值显然是\(dp_{1,j,d[1],g_{j,0,d[1],1}}=1\)。
转移的话，一定是从\(dp_{i',j,p,x}\)转移到\(dp_{i,j-1,max(p,d),g_{j-1,p,d,x}}\)，其中\(i'<i\)。这个可用前缀和优化。

时空复杂度：\(O(nk^2(n+k))\)。

Code

#include <cstdio>

#include <cstring>

#define max(x,y) ((x)>(y)?(x):(y))

#define fo(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int N=505,K=11,mo=998244353;

int n,k,g[N][K][K][K],u,d[N],x,y,ti,dfn[N],dp[N][N][K][K],ans;

bool e[N][N];

void P(int&x,int y) {x=(x+y)%mo;}

void dfs(int u,int fa)

{

	if(!ti++)

		fo(j,1,n)

		{

			int x=g[j][0][d[u]][1];

			dp[ti][j][d[u]][x]=1;

		}

	else

		fo(j,2,n) fo(p,0,k-1) fo(x,0,k-1)

		{

			int p1=max(p,d[u]), x1=g[j-1][p][d[u]][x];

			if(~x1) P(dp[ti][j-1][p1][x1],(mo+dp[ti-1][j][p][x]-dp[dfn[fa]-1][j][p][x])%mo);

			P(dp[ti][j-1][p][x],dp[ti-1][j-1][p][x]);

		}

	fo(x,d[u],k-1) P(ans,(mo+dp[ti][1][x][d[u]]-dp[ti-1][1][x][d[u]])%mo);

	dfn[u]=ti;

	fo(v,1,n) if(v^fa&&e[u][v]) dfs(v,u);

}

int main()

{

	freopen("buried.in","r",stdin);

	freopen("buried.out","w",stdout);

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

	memset(g,-1,sizeof g);

	fo(p,0,k-1)

	{

		g[1][p][0][0]=0;

		fo(x,0,k-1)

			if(p|x)

			{

				int y=x;

				while(y<k)

				{

					g[1][p][y][x]=y;

					y+=max(p,y);

				}

				g[2][p][1][x]=y-k;

			}

	}

	fo(i,2,n)

		fo(p,0,k-1)

			fo(a,0,k-1)

			{

				g[i][p][0][a]=a;

				if(!~(u=g[i][p][1][a])) continue;

				fo(x,2,k-1) if(!~(u=g[i][p][x][a]=g[i][max(p,x-1)][1][u])) break;

				if(~u) g[i+1][p][1][a]=g[i][k-1][1][u];

			}

	fo(i,1,n) scanf("%d",&d[i]);

	fo(i,1,n-1) scanf("%d%d",&x,&y),e[x][y]=e[y][x]=1;

	dfs(1,0);

	printf("%d",ans);

}

巴特西

【GMOJ6377】幽曲[埋骨于弘川]

Description

Solution

Code

最新文章

热门文章