[loj2473]秘密袭击

容易发现答案即$\sum_{S}\sum_{u=1}^{W}[u\le val(S)]=\sum_{u=1}^{W}\sum_{S}[u\le val(S)]$，那么可以枚举权值$u$，并将点权$val<u$的点标为0，$u\le val$的点标为1，相当于统计大于等于k个1的连通子图个数

考虑dp，用$f[u][i][j]$表示权值为u，在以i为根的子树中，选出点中恰好有j个1的方案数，转移方程为$f[u][i][j]=\sum_{a[i]+\sum_{son}b[son]=j}\prod_{son}(f[u][son][b[son]]+[b[son]==0])$，复杂度为$o(w\cdot n^{3})$

令$F[u][i](x)=\sum_{j=0}^{sz[i]}f[u][i][j]\cdot x^{j}$，那么$F[u][i](x)=x^{a[i]}\prod_{son}(F[u][son](x)+1)$，对其插值，最后再用拉格朗日插值法求出系数（先把所有多项式加起来再求），复杂度为$o(w\cdot n^{2})$

调换枚举顺序，对于一个插值，将每一个点i以u为下标建立一棵线段树，由于如果i子树内不存在某一个权值w，那么显然有$F[w][i]=F[w-1][i]$，因此可以线段树合并来实现dp过程，总复杂度$o(n^{2}log W)$

由于线段树合并时还需要实现累加子树内的多项式，这可以通过记录4个标记$(a,b,c,d)$来实现，其中a和b表示这个点的答案，c和d表示累加起来的答案，最后标记都下传后的d标记即为这个位置上所有数的和

  1 #include<bits/stdc++.h>

  2 using namespace std;

  3 #define N 2005

  4 #define mod 64123

  5 #define mid (l+r>>1)

  6 struct ji{

  7     int nex,to;

  8 }edge[N<<1];

  9 struct tag{

 10     int a,b,c,d;

 11 }f[N*15];

 12 int V,E,n,m,w,v,x,y,ans,head[N],r[N],a[N],b[N],sum[N],ch[N*15][2];

 13 void add(int x,int y){

 14     edge[E].nex=head[x];

 15     edge[E].to=y;

 16     head[x]=E++;

 17 }

 18 int ksm(int n,int m){

 19     if (!m)return 1;

 20     int s=ksm(n,m>>1);

 21     s=1LL*s*s%mod;

 22     if (m&1)s=1LL*s*n%mod;

 23     return s;

 24 }

 25 int New(){

 26     f[++V]=tag{1,0,0,0};

 27     ch[V][0]=ch[V][1]=0;

 28     return V;

 29 }

 30 void upd(int &k,tag x){

 31     if (!k)k=New();

 32     f[k].c=(1LL*f[k].a*x.c+f[k].c)%mod;

 33     f[k].d=(1LL*f[k].b*x.c+f[k].d+x.d)%mod;

 34     f[k].a=1LL*f[k].a*x.a%mod;

 35     f[k].b=(1LL*f[k].b*x.a+x.b)%mod;

 36 }

 37 void down(int k){

 38     upd(ch[k][0],f[k]);

 39     upd(ch[k][1],f[k]);

 40     f[k]=tag{1,0,0,0};

 41 }

 42 void update(int &k,int l,int r,int x,int y,tag z){

 43     if ((l>y)||(x>r))return;

 44     if (!k)k=New();

 45     if ((x<=l)&&(r<=y)){

 46         upd(k,z);

 47         return;

 48     }

 49     down(k);

 50     update(ch[k][0],l,mid,x,y,z);

 51     update(ch[k][1],mid+1,r,x,y,z);

 52 }

 53 int merge(int k1,int k2){

 54     if ((!k1)||(!k2))return k1+k2;

 55     if ((!ch[k1][0])&&(!ch[k1][1]))swap(k1,k2);

 56     if ((!ch[k2][0])&&(!ch[k2][1])){

 57         f[k1].a=1LL*f[k1].a*f[k2].b%mod;

 58         f[k1].b=1LL*f[k1].b*f[k2].b%mod;

 59         f[k1].d=(f[k1].d+f[k2].d)%mod;

 60         return k1;

 61     }

 62     down(k1);

 63     down(k2);

 64     ch[k1][0]=merge(ch[k1][0],ch[k2][0]);

 65     ch[k1][1]=merge(ch[k1][1],ch[k2][1]);

 66     return k1;

 67 }

 68 void dfs(int k,int fa){

 69     upd(r[k],tag{0,1,0,0});

 70     for(int i=head[k];i!=-1;i=edge[i].nex)

 71         if (edge[i].to!=fa){

 72             dfs(edge[i].to,k);

 73             r[k]=merge(r[k],r[edge[i].to]);

 74         }

 75     update(r[k],1,w,1,a[k],tag{v,0,0,0});

 76     upd(r[k],tag{1,0,1,0});

 77     upd(r[k],tag{1,1,0,0});

 78 }

 79 void tot(int k,int l,int r){

 80     if (l==r){

 81         sum[v]=(sum[v]+f[k].d)%mod;

 82         return;

 83     }

 84     down(k);

 85     tot(ch[k][0],l,mid);

 86     tot(ch[k][1],mid+1,r);

 87 }

 88 int main(){

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

 90     memset(head,-1,sizeof(head));

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

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

 93         scanf("%d%d",&x,&y);

 94         add(x,y);

 95         add(y,x);

 96     }

 97     for(v=0;v<=n;v++){

 98         V=0;

 99         memset(r,0,sizeof(r));

100         dfs(1,0);

101         tot(r[1],1,w);

102     }

103     memset(a,0,sizeof(a));

104     a[0]=1;

105     for(int i=0;i<=n;i++)

106         for(int j=i+1;j>=0;j--)a[j]=(a[j-1]-i*a[j]%mod+mod)%mod;

107     for(int i=0;i<=n;i++){

108         x=1;

109         for(int j=0;j<=n;j++)

110             if (i!=j)x=1LL*x*(i-j+mod)%mod;

111         x=1LL*ksm(x,mod-2)*sum[i]%mod;

112         memcpy(b,a,sizeof(b));

113         for(int j=n+1;j;j--){

114             b[j-1]=(b[j-1]+i*b[j])%mod;

115             if (m<j)ans=(ans+1LL*b[j]*x)%mod;

116         }

117     }

118     printf("%d",ans);

119 }

巴特西

[loj2473]秘密袭击

最新文章

热门文章