hdu 6399 City Development

读进来可能会有相同的\(n_i\),不过在相同的\(n_i\)中只有最后一个是有用的,所以其他的要缩起来,缩完后这些\(n\)的数量不会超过19个

可以发现一个城市的答案为所有城市初始权值的线性组合,然后对于\(x\),其他和\(x\)gcd深度相同的点转移系数都是一样的,因为gcd深度相同那么转移也是本质相同的

那么考虑构造转移矩阵,\(a_{i,j}\)表示gcd深度为\(i\)转移到深度为\(j\)的方案数,那么答案即为\(ans_x=\sum_{i=1}^{n} d_x {f^T}_{\gcd(x,i),m}\)(当然gcd相同的要一起统计)

先考虑\(i\neq j\)的情况,这个时候无论是哪个点对转移系数都是\(p_{\min(i,j)}\),然后还要乘上gcd深度为\(j\)的点数,即为\(p_{\min(i,j)}(n_j-n_{j+1})\)

然后是\(i=j\)的情况.可以发现从一个深度为\(i\)的点到深度相同的点,这两点之间的lca深度有\(m,m-1,m-2...i\).对于\(>i\)的部分,这些是和\(i\neq j\)类似的,即\(\sum_{k=i+1}^{m} p_{k}(n_k-n_{k+1})\).但如果是\(=i\),那么可以到达的点数是多了\(n_{i+1}\)的,这一部分也是到\(x\)gcd深度\(>i\)的部分,所以这部分为\(p_{i}(n_i-2n_{i+1})\)

//以下是在laji hduPE的代码

#include<bits/stdc++.h>

#define LL long long

#define uLL unsigned long long

#define db long double

using namespace std;

const int N=3e5+10,mod=998244353;

LL rd()

{

	LL x=0,w=1;char ch=0;

	while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

	return x*w;

};

int n,m,d[N],c[N];

LL T,a[N];

struct matrix

{

	int a[22][22];

	matrix(){memset(a,0,sizeof(a));}

	matrix operator * (const matrix &bb) const

    {

		matrix an;

		for(int i=0;i<=m;++i)

			for(int j=0;j<=m;++j)

			{

				LL nw=0;

				for(int k=0;k<=m;++k) nw+=1ll*a[i][k]*bb.a[k][j]%mod;

				an.a[i][j]=nw%mod;

			}

		return an;

	}

	matrix operator ^ (const LL &bb) const

	{

		matrix an,a=*this;

		for(int i=0;i<=m;++i) an.a[i][i]=1;

		LL b=bb;

		while(b)

		{

			if(b&1) an=an*a;

			a=a*a,b>>=1;

		}

		return an;

	}

}bb;

int main()

{

	int K=rd();

	while(K--)

	{

		memset(bb.a,0,sizeof(bb.a));

		n=rd(),m=rd(),T=rd();

		d[0]=n;

		for(int i=1;i<=m;++i) d[i]=rd();

		d[m+1]=0;

		for(int i=1;i<=n;++i) a[i]=a[i-1]+rd();

		for(int i=0;i<=m;++i) c[i]=rd();

		int nn=m;

		m=-1;

		for(int i=0;i<=nn;++i)

			if(d[i]!=d[i+1]) d[++m]=d[i],c[m]=c[i];

		d[m+1]=0;

		for(int i=0;i<=m;++i)

			for(int j=0;j<=m;++j)

			{

				if(i==j)

				{

					for(int k=m;k>i;--k)

						bb.a[i][j]=(bb.a[i][j]+1ll*c[k]*(d[k]-d[k+1])%mod)%mod;

					bb.a[i][j]=(bb.a[i][j]+1ll*c[i]*(d[i]-d[i+1]-d[i+1])%mod)%mod;

				}

				else bb.a[i][j]=1ll*c[min(i,j)]*(d[j]-d[j+1])%mod;

			}

		bb=bb^T;

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

		{

			int ll=2,rr=1,an=0;

			for(int j=m;~j;--j)

			{

				int r=(i+d[j]-1)/d[j]*d[j],l=r-d[j]+1;

				an=(an+((a[r]-a[l-1])-(a[rr]-a[ll-1]))%mod*bb.a[j][m]%mod)%mod;

				ll=l,rr=r;

			}

			printf("%d",an);

			if(i<n) putchar(' ');

		}

		if(K) puts("");

	}

	return 0;

}

巴特西

hdu 6399 City Development

最新文章

热门文章