题面保证“在实际的测试点中，T 组数据的 K 都是相同的”。

但是extra test 1并不满足这个性质。

能否予以修正？ @whzzt

题目链接

官方题解链接

"平衡树启发式分离 $n$ 个元素的时间复杂度也是 $O(nlogn)$ 的”需要每次分离的集合都是有序的。

然后在本题中，每次分离的集合A并不是有序的，如果直接用快排，那复杂度为$AlogA$，于是复杂度变成了$O(nklog^2n)$。

这可咋办？

http://uoj.ac/submission/320603 http://uoj.ac/submission/320616

两份一模一样的代码，一份40分，一份0分，为啥？

官方题解最后是3^n，可以加以优化。

题解最后有一步枚举非叶子集合及其超集。

但注意对于一个确定的非叶子集合，枚举的叶子贡献的方案数是独立的。

所以不需要枚举超集，只需要知道选了奇数或偶数个叶子的总方案数。于是这一部分复杂度就从$3^n$变成$n2^n$。

还有一个部分是计算给定点集的生成基环树的方案数。

这部分题解有所提及，“我们考虑有向图中的基环外向树可以看成就是每一个点恰好连出去一条边”“答案似乎是度数的乘积”。

这样有两个问题：1.这样算出来的是基环外向树森林的个数，而不是树；2.因为是无向边，所以可能有相邻的两个点选中了同一条边。

第一个问题，可以通过集合幂级数求ln来解决，复杂度$n^22^n$。

第二个问题，多算的方案，等价于从一棵生成树上选中一条边成为重边，方案数即为生成树个数*（点数-1），复杂度$n^32^n$

最后总复杂度就是$n^32^n$，比题解的$3^n$要优越，跑得也更快。

提交记录

好像loj管理员@liu_cheng_ao 自己都没来推荐，那就让我来吧。比赛链接：https://loj.ac/article/236

（蒟蒻写的博客，如有不妥，请轻喷）
我的想法是设f[i][j][l]表示审到第i道题，i-k+1到i中最难（若难度系数相等则比较下标大小）的是第j道题，且难度系数为l。其实注意到答案是期望乘上$n^n$，等价于求出所有可能情况的劳累度之和， 然后就是转移，~丢代码跑~~
首先，我们考虑就$j\lt k$的情况,显然此时$f[i][j][l]=f[i-1][j+1][l]乘(l-1)乘w[l]$, 直接从前面继承 但这是不够的，因为i-k+1到i的最大值可能在i-k到i-1中是次大值，被i-k给压制着，所以还要考虑f[i-1][1][p]的情况（其中p为l+1到n的一个数）则i-k的位置是p，且i-k+1到j均小于等于的概率为$l^(j-1)乘(l-1)^(k-j)乘(p-1)^(1-k)$，之后f[i][j][l]+=概率乘[i-1][1][p]乘w[l]即可

同样的， 然后对于$j==k$的情况，除了继承，还要考虑i-k+1上的数大于i位置上的数

#include<cstdio>
typedef long long ll;
const int N=402;
const ll mo=998244353;
ll pow(ll x,int y){
    if(y==0)return 1;
    ll u=pow(x,y>>1);
    if(y&1)return u*u%mo*x%mo;
        else return u*u%mo;

}
int n,k,i,j,l,f[N][N][N],w[N],o,p;
ll x,inv[N],y,z,mm[N][N],inm[N][N];
int main(){
    //freopen("a.txt","r",stdin);
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;++i)scanf("%d",w+i);
    for(i=1;i<=k;++i)
        for(j=1;j<=n;++j){
            x=1ll*w[j]*pow(j,i-1)%mo*pow(j-1,k-i)%mo;
            f[k][i][j]=x;
        }
    for(i=1;i<=n;++i)inv[i]=pow(i,mo-2);
    for(i=1;i<=n;++i){
        mm[i][0]=1;
        inm[i][0]=1;
        for(j=1;j<=n;++j)mm[i][j]=mm[i][j-1]*i%mo,inm[i][j]=pow(mm[i][j],mo-2);
    }
    **inm=**mm=1;
    for(i=k+1;i<=n;++i){
        for(j=1;j<k;++j)
            for(l=1;l<=n;++l){
                if(l==1)continue;
                x=1ll*(l-1)*f[i-1][j+1][l]%mo*w[l]%mo;
                for(p=l+1;p<=n;++p){
                    y=inm[p-1][k-1];
                    z=mm[l][j-1]*mm[l-1][k-j]%mo;
                    x=(x+1ll*f[i-1][1][p]*w[l]%mo*y%mo*z%mo)%mo;
                }
                //for(p=2;p<=l;++p)x=(x+1ll*f[i-1][1][p]*w[l])%mo;
                f[i][j][l]=x;
            }
        for(l=1;l<=n;++l){
            x=0;
            for(o=2;o<=k;++o)
                for(p=1;p<=l;++p)
                    x=(x+1ll*f[i-1][o][p]%mo*w[l]%mo)%mo;
            for(p=1;p<=l;++p)x=(x+1ll*f[i-1][1][p]*w[l])%mo;
            for(p=l+1;p<=n;++p){
                y=inm[p-1][k-1];
                z=mm[l][j-1]*mm[l-1][k-j]%mo;
                x=(x+1ll*f[i-1][1][p]*w[l]%mo*y%mo*z%mo)%mo;
            }
            f[i][k][l]=x;
        }
    }
    x=0;
    /*for(i=1;i<=n;++i)
        for(j=1;j<=k;++j)
            for(l=1;l<=n;++l)printf("f[%d][%d][%d]==%d\n",i,j,l,f[i][j][l]);*/
    for(i=1;i<=k;++i)
        for(j=1;j<=n;++j)x=(x+f[n][i][j])%mo;
    printf("%lld\n",(x%mo+mo)%mo);
    return 0;
}

然而这只能拿70分，正是题解中所谓的“部分分算法比标算麻烦” 仔细观察代码，发现是可以前缀和的优化 f是原始的DP数组 f2是前两维固定，第3维的前缀和 f3是前两维固定,f[i][j][k]/((j-1)^k)的前缀和

#include<cstdio>
typedef long long ll;
const int N=402;
const ll mo=998244353;
ll pow(ll x,int y){
    if(y==0)return 1;
    ll u=pow(x,y>>1);
    if(y&1)return u*u%mo*x%mo;
        else return u*u%mo;

}
int n,k,i,j,l,ff[2][N][N],w[N],o,p,ff2[2][N][N],ff3[2][N][N],*f[N],*g[N],*t[N],*f2[N],*g2[N],*f3[N],*g3[N];
ll x,inv[N],y,z,mm[N][N],inm[N][N];
inline void swap(){
    for(int i=0;i<N;++i){
        t[i]=f[i];
        f[i]=g[i];
        g[i]=t[i];
        t[i]=f2[i];
        f2[i]=g2[i];
        g2[i]=t[i];
        t[i]=f3[i];
        f3[i]=g3[i];
        g3[i]=t[i];
    }
}
int main(){
    //freopen("a.txt","r",stdin);
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;++i)scanf("%d",w+i);
    for(i=1;i<=n;++i){
        f[i]=ff[0][i];
        g[i]=ff[1][i];
        f2[i]=ff2[0][i];
        g2[i]=ff2[1][i];
        f3[i]=ff3[0][i];
        g3[i]=ff3[1][i];
    }
    for(i=1;i<=k;++i)
        for(j=1;j<=n;++j){
            x=1ll*w[j]*pow(j,i-1)%mo*pow(j-1,k-i)%mo;
            f[i][j]=x;
        }
    for(i=1;i<=n;++i)inv[i]=pow(i,mo-2);
    for(i=1;i<=n;++i){
        mm[i][0]=1;
        inm[i][0]=1;
        for(j=1;j<=n;++j)mm[i][j]=mm[i][j-1]*i%mo,inm[i][j]=pow(mm[i][j],mo-2);
    }
    **inm=**mm=1;
    for(j=1;j<=k;++j)
        for(l=1;l<=n;++l){
            //printf("f[2][%d][%d]==%d\n",j,l,f[j][l]);
            f2[j][l]=1ll*(f2[j][l-1]+f[j][l])%mo,f3[j][l]=1ll*(f3[j][l-1]+f[j][l]*inm[l-1][k-1])%mo;
        }
    for(i=k+1;i<=n;++i){
        swap();    
        for(j=1;j<k;++j)
            for(l=2;l<=n;++l){
                x=1ll*(l-1)*g[j+1][l]%mo*w[l]%mo;
                x=(x+1ll*(g3[1][n]-g3[1][l]+mo)%mo*mm[l][j-1]%mo*mm[l-1][k-j]%mo*w[l]%mo)%mo;
                f[j][l]=x;
            }
        for(l=1;l<=n;++l){
            x=0;
            for(o=2;o<=k;++o)
                x=(x+1ll*g2[o][l]%mo*w[l]%mo)%mo;
            x=(x+1ll*g2[1][l]*w[l])%mo;
            for(p=l+1;p<=n;++p){
                y=inm[p-1][k-1];
                z=mm[l][j-1]*mm[l-1][k-j]%mo;
                x=(x+1ll*g[1][p]*w[l]%mo*y%mo*z%mo)%mo;
            }
            f[k][l]=x;
        }
        for(j=1;j<=k;++j)
            for(l=1;l<=n;++l){
                f2[j][l]=1ll*(f2[j][l-1]+f[j][l])%mo,f3[j][l]=1ll*(f3[j][l-1]+f[j][l]*inm[l-1][k-1])%mo;
            //    printf("f[%d][%d][%d]==%d\n",i,j,l,f[j][l]);
            }
    }
    x=0;
    for(i=1;i<=k;++i)
        for(j=1;j<=n;++j)x=(x+f[i][j])%mo;
    printf("%lld\n",(x%mo+mo)%mo);
    return 0;
}

然后代码长度就到了2.1KB，倒数几名。

vfk的官方题解提供了一种单调队列合并的做法（解法5-2），但给的复杂度式子是O(n+qlogn)，也就是说预处理时间是O(n)。我不太理解。 然后我想了一种构造方法：对于n个点的树，根的左儿子是一条长为n/2-1的链，右儿子则递归处理。然后每个点的w值赋成其深度。 这样，根据xllend3大爷的代码，每次合并至少是O(轻儿子的单调队列长度之和）。 所以，对于这种树，我们有f(n)=f(n/2)+n/2=f(n/2)+O(n),所以f(n)=O(nlogn) 那么，为什么预处理时间是O(n)，我错在哪里？

这题该怎么做啊？