hdu 6399 City Development

vjudge

读进来可能会有相同的\(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

原文：https://www.cnblogs.com/smyjr/p/11574185.html