Access Globe 最近正在玩一款战略游戏。在游戏中，他操控的角色是一名C 国士 兵。他的任务就是服从指挥官的指令参加战斗，并在战斗中取胜。

C 国即将向D 国发动一场秘密袭击。作战计划是这样的：选择D 国的s 个城市， 派出C 国战绩最高的s 个士兵分别秘密潜入这些城市。每个城市都有一个危险程度d_idi​，

C 国指挥官会派遣战绩最高的士兵潜入所选择的城市中危险程度最高的城市，派遣战绩第二高的士兵潜入所选择的城市中危险程度次高的城市，以此类推（即派遣战绩第i高的士兵潜入所选择城市中危险程度第i 高的城市）。D 国有n 个城市，n - 1 条双向道路连接着这些城市，使得这些城市两两之间都可以互相到达。为了任务执行顺利，C 国选出的s 个城市中，任意两个所选的城市，都可以不经过未被选择的城市互相到达。

Access Globe 操控的士兵的战绩是第k 高，他希望能估计出最终自己潜入的城市的 危险程度。Access Globe 假设C 国是以等概率选出任意满足条件的城市集合S ，他希望你帮他求出所有可能的城市集合中，Access Globe 操控的士兵潜入城市的危险程度之和。如果选择的城市不足k 个，那么Access Globe 不会被派出，这种情况下危险程度为0。

当然，你并不想帮他解决这个问题，你也不打算告诉他这个值除以998 244 353 的 余数，你只打算告诉他这个值除以64,123 的余数。

Solution

首先做第一步转化，就是考虑每个点会被选择多少次，算出来之后求个和就行了。

为了方便处理(由于是暴力)，我们枚举每个点，然后对这个点做一遍树形dp，就设dp[i][j]表示包含i的联通块且i为联通块中深度最小的点，子树中点权大于等于d[root]的点的个数为j的联通块个数。

转移就是我们平常写的那种树形背包。

然后我发现了一个问题，就是对于一个点对ij且d[i]=d[j]时，包含它们的联通块在枚举i和j时都会被枚举到一次，答案就会算多。

如果做题比较多的话就可以想到，我们可以钦定当d[i]=d[j]时，i对j存在贡献当且仅当i<=j。

然后这题就做完了。

卡边界的时候要注意判不合法。

Code

#include
     
      #include
      
       #include
       
        #define N 1669using namespace std;typedef long long ll;const int mod=64123;ll dp[N][N],g[N],d[N];int tot,size[N],head[N],root,n,k,w,ans;inline ll rd(){    ll x=0;char c=getchar();bool f=0;    while(!isdigit(c)){
   if(c=='-')f=1;c=getchar();}    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}    return f?-x:x;}struct node{    int n,to;}e[N<<1];inline void add(int u,int v){    e[++tot].n=head[u];    e[tot].to=v;    head[u]=tot;}void dfs(int u,int fa){    size[u]=d[u]>d[root]?1:0;    if(d[u]==d[root]&&u<=root)size[u]=1;    dp[u][size[u]]=1;dp[u][!size[u]]=0;    for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa){        int v=e[i].to;dfs(v,u);        for(int j=0;j<=size[u];++j)g[j]=dp[u][j];        for(int j=1;j<=size[v];++j)g[size[u]+j]=0;        for(int j=0;j<=size[u];++j)          for(int k=0;k<=size[v];++k)(g[j+k]+=dp[u][j]*dp[v][k])%=mod;        size[u]+=size[v];        for(int j=0;j<=size[u];++j)dp[u][j]=g[j];    } }int main(){    n=rd();k=rd();w=rd();int x,y;    for(int i=1;i<=n;++i)d[i]=rd();    for(int i=1;i
       
      
     

 UPD：

又去研究了一下正解 。

首先转化题目条件。

先枚举一个i

∑cnt[i]*i 这里的cnt[i]表示联通块内权值等于i的联通块个数有多少个。

然后再去转化一步

∑cnt[i]这里的cnt[i]表示联通块内权值大于等于i的联通块个数有多少个。

我们发现权值为i的联通块刚好被算了i次，所以这样就把后面乘的数去掉了。

然后考虑设计状态，dp[i][j][k]表示以i为根的子树，当前dp的是大于等于j的联通块，联通块内权值大于等于j的联通块个数。

转移就像背包一样。

但这样的话我们需要dpj次(虽然这样也能过。

考虑它的转移，每一步的转移都是相似的

然后可以用整体dp的思想，把所有的dp状态放在一起，然后这些东西一起转移。

用线段树合并维护。

然后背包的卷积用FFT。

然而这样复杂度还是爆炸。

考虑到FFT的复杂度瓶颈在点值转换和插值转换，所以我们可以先在一开始处理出点值表达。

然后每次的合并都是按位的。

随后再插回去。

所以我们考虑生成函数，也就是f[i][j]是一个最高次为n的多项式。

然后我们考虑带入(1~n+1)获得n+1个点值表达，随后做插值。

那么具体的dp值如何维护呢。

首先我们线段树的下标是j，里面是一个多项式。

我们记一个f数组，一个g数组

那么维护方法就是设置一个变换(a,b,c,d),令初始为(f,g)

(f,g)->(f*a+b,c*f+b+d)。

初始(1,0,0,0)也就是任何东西经过这个变换值都不变。

然后b代表的是f，d代表的是g，这样我们就不用管(f,g)了。

对于每个节点，初值为(0,1,0,0)

然后线段树合并时每个节点乘一个(y.b,0,0,y.d)

然后其他合并时的转移可以手推一下。

直接说最后的插值吧。

 

这是直接求最后多项式的式子。

和单点求值的原理一样，也是构造，当x取xi时，这一项答案为yi,其余都是0.

w可以通过n^2的多项式乘法求出。

因为多乘了多以要除回来一个，

a[i]就是这个式子剩下的，也可以n^2算。

令F*(x-xi)=W

F[k-1]-xi*F[k]=W

F[k]=(F[k-1]-W[k])/xi

代码

#include
     
      #include
      
       #include
       
        #define N 1700#define ls tr[cnt].l#define rs tr[cnt].rusing namespace std;//typedef unsigned int ll;typedef long long ll;const ll mod=64123;int tott,head[N],tot,rt[N],w,n,k,a[N];ll ans[N],ni[mod+2];inline ll rd(){    ll x=0;char c=getchar();bool f=0;    while(!isdigit(c)){
   if(c=='-')f=1;c=getchar();}    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}    return f?-x:x;}struct node{    ll a,b,c,d;    node(ll aa=1,ll bb=0,ll cc=0,ll dd=0){a=aa;b=bb;c=cc;d=dd;}    void clear(){a=1;b=c=d=0;}    node operator *(const node &x)const{
   return node{a*x.a%mod,(x.a*b%mod+x.b)%mod,(x.c*a%mod+c)%mod,((d+x.d)%mod+x.c*b%mod)%mod};}};struct segment{
   int l,r;node val;}tr[N*50];struct edge{
   int n,to;}e[N<<1];inline void add(int u,int v){e[++tot].n=head[u];e[tot].to=v;head[u]=tot;}inline void pushdown(int cnt){    if(!ls)ls=++tott;    if(!rs)rs=++tott;    tr[ls].val=tr[ls].val*tr[cnt].val;    tr[rs].val=tr[rs].val*tr[cnt].val;    tr[cnt].val.clear();}void upd(int &cnt,int l,int r,int L,int R,node x){    if(!cnt)cnt=++tott;     if(l>=L&&r<=R){tr[cnt].val=tr[cnt].val*x;return;}    int mid=(l+r)>>1;    pushdown(cnt);    if(mid>=L)upd(ls,l,mid,L,R,x);    if(mid
        
         >1;    return (query(ls,l,mid)+query(rs,mid+1,r))%mod;}ll f[N],res[N],aa[N],tmp[N];inline ll calc(){    f[0]=1;    ll as=0;    for(int i=1;i<=n+1;++i){        for(int j=n+1;j>=1;--j){            f[j]=(f[j-1]+(mod-i)*f[j]%mod)%mod;        }        f[0]=f[0]*(mod-i)%mod;    }    for(int i=1;i<=n+1;++i){        aa[i]=ans[i];        for(int j=1;j<=n+1;++j)          if(i!=j)aa[i]=aa[i]*ni[(i-j+mod)%mod]%mod;          }    for(int i=1;i<=n+1;++i){        tmp[0]=(mod-f[0])*ni[i]%mod;        for(int j=1;j<=n;++j)tmp[j]=(tmp[j-1]-f[j]+mod)%mod*ni[i]%mod;        for(int j=1;j<=n;++j)tmp[j]=tmp[j]*aa[i]%mod,(res[j]+=tmp[j])%=mod;    }    for(int i=k;i<=n;++i)(as+=res[i])%=mod;    return as;}int main(){    freopen("1.in","r",stdin);    n=rd();k=rd();w=rd();    for(int i=1;i<=n;++i)a[i]=rd();    int u,v;    for(int i=1;i