UOJ Logo zx2003的博客

博客

UNR#2 Day2T1的一些其他做法

2017-07-15 16:35:17 By zx2003

(蒟蒻写的博客,如有不妥,请轻喷)
我的想法是设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,倒数几名。

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。