UOJ Logo zx2003的博客

博客

标签
暂无

关于 [JSOI2019]节日庆典 的一个线性做法

2019-06-01 20:48:08 By zx2003

题目链接

很久以前我想过这个问题,但当时没有什么好的办法。

昨天去做了下江苏省选二轮的题,发现居然被出出来了。

看到问题后一个自然的想法是求出每个前缀的lyndon word分解(模板题在此)。

但是博主只知道Duval算法(可以看鏼爷论文),然后该算法需要在字符串结尾补$ - \infty $字符,如果要求出每个前缀的lyndon word分解,原来的均摊分析就失效了。

回忆一下Duval算法的过程,前缀$i$做完之后是(若干已经做好的)+(某个串s)重复t遍+s的某个前缀u。

可以证明,已经做好的部分对答案没有影响,(某个串s)重复t遍对答案有影响的部分只有第一次出现的位置,而$u$整个串都可能对答案有影响。

怎么办?

一个想法是,那就同时维护出串$u$,在执行Duval算法后的状态。

但是串$u$执行完Duval算法后会得到一个串u',我们需要递归执行前述的过程。

容易发现$|u| \le |s| \le \frac{i}{2}$,所以这个“递归”只会有 $logn$ 层。

具体实现可以参考这份代码

让我们思考一些可能的优化。

首先一个想法是,在Duval算法运行过程中,既然串$u$在之前已经出现过了,那么是不是可以复用之前的运算结果?

记串u第一次出现的位置的结尾处为$x$

也就是说,我们猜想$ans_i=min(串s第一次出现的位置的开头,ans_x)$,注意这里的$ans_i$可以认为是$i$-题目要求输出的真实的答案。

如果这样不对,那么必然存在两个位置$p$和$q$使得前缀$x$从$p$开始和从$q$开始的循环移位都是相等的。

否则这两个位置开始的循环移位在$x$之前已经比出大小,从$x$扩展到$i$不会对大小比较产生影响。

从而前缀$x$构成的串存在非平凡整循环节$y$。

同理可以证明$y$也存在非平凡整循环节.

如此递归下去,可以得到串$x$字符全部相等,此时我们可以平凡地验证结论的正确性。

有了这个结论,配合线性SA和$O(n)-O(1)$RMQ,我们可以获得本题的一个线性算法。

不过线性SA和$O(n)-O(1)$RMQ太难写了,博主写不动。

由于lyndon word的性质和Duval算法的正确性,在处理前缀$i$的答案时,$ans_x$所对应的后缀必然大于等于串s的等长前缀。

所以我们只需使用字符串哈希判定子串相等,之后便转化为了一个子串和原串比较大小,这可以通过exkmp来线性实现。

最后提交在这里,好像比$O(nlogn)$还慢。

如果本文论述出现了漏洞,欢迎读者指出。

PS: 听说16年有篇论文提出了关于子串最小循环的$O(n)-O(1)$算法,感觉本文可能只在OI中有用。

CTS2019D2T2的一种非标算做法

2019-05-14 19:32:02 By zx2003

下午上台发言的时候有点呆滞,感觉讲的东西自己都听不懂。可能讲课水平不太行。

首先考虑计数所有子串均大于等于s的串的个数。

然后对串s建立KMP自动机,补齐26n条转移边的那种。

注意根据题意,部分跳回根的转移边是不合法的

之后枚举在自动机里走了无穷多个串s之后到达的节点是点u。

由这个定义,在自动机里,从点u出发行走完一个完整的串s之后,会回到点u自己。

于是我们只要解决在一张有向图上,一个点出发走m步回到自己的方案数即可。单次复杂度$O(m * n * 26)$

由于还要枚举点u,所以总的复杂度是$O(n^2m * 26)$

而且可以发现这个算法并不依赖于n与m的大小关系。

这样我们就能获得60分啦

实际上这个算法是有漏洞的。

一个点每条转移边并不是都能走。

想像一下,串s形如abdabc,我们现在在长度为5的前缀对应的节点上。

如果下一个字符是c,那么在这个无穷循环串中,我们就会获得一个子串abc,显然由此可以导出一个比s小的子串。

所以,每个点上所有不是跳回根的转移边只有字符最大的一条有用。

如果从根出发只走这样的转移边,那么会形成一个rho的形状。

考虑在这个rho上计数。

我们先算出$f_{i,j}$表示从根出发走i步,走到节点j的方案数。这一部分复杂度$O(nm)$。

然后还是跟之前一样枚举节点u。

如果u不经过根,那么路径唯一,方案数可以$O(1)$计算。

如果u经过根,那么枚举从u出发走几步才跳回根。这一部分复杂度也是$O(nm)$。

最后该算法总复杂度为$O(mn)$。

感觉rho的结构挺简洁的吧,不过考场上由于某些原因,并没有考虑过改进复杂度。

有没有老哥来把前面这个算法优化一下啊?

upd:

可能是可以优化的。

设生成函数F满足$f_i$为从根出发走$i$步第一次走回根的方案数。

F是可以直接在KMP过程中计算的。

所有节点走$m$步并且经过根的总方案数应该是$[x^m] (F' * x -F +1) * \frac{1}{1-F}$

复杂度应该是$O(n+mlogm)$。

十二省联考D2T3 hope 不用求逆的做法

2019-04-12 18:15:28 By zx2003

大概有两种,第一种是魔改原官方题解做法,第二种则是直接避免(求出每个点的子树答案)。


算法一

2019.6.1upd:他假了,原因可以见lca的回复

在长链剖分的时候我们需要维护一个类似与滑动窗口的东西。

每次从滑动窗口里踢掉一个东西的时候,我们需要求出这个元素的真实值,官方题解在这里需要求逆。

但实际上每次遇到这种情况暴力$O(L)$地下传标记复杂度是对的。

证明的大概思路是,这样做的复杂度是链长+$\sum 每相邻两次的重叠长度$,然后对于每次重叠,一定存在一个短子树的深度大于等于重叠长度。

所以复杂度与长链剖分相同,仍为$O(n)$


算法二

一个自然的想法是通过树分治来规避求逆元。

但是一个很大的问题在于,我们仍然需要求出子连通块中的某个点到分治中心的答案,而且这一步相对于原问题没有任何简化。

我们能不能简化这一步呢?

注意到如果连通块直径不超过$L$,那么这一步是可以简单树上DP来完成的。

这就启示我们使用Top cluster 剖分。

我们可以将原树分割成$O(\frac{n}{L})$个直径不超过$L$的簇。

对于每个簇,可以预处理出,在簇的内部,两个端点的DP数组。

簇与簇之间的影响需要$O(\frac{n}{L})$次合并DP数组来计算。

合并两个DP数组的复杂度为$O(L)$,最后总复杂度为$O(\frac{n}{L} * L)=O(n)$


但是好像想要出个不能求逆的加强版比较困难,博主一时没想到有什么,不可逆,性质恰到好处,在本题中还能方便维护的信息。

算法一没有实现过,但应该是对的(吧)。

算法二的实现在这里->链接

由于滥用vector导致常数巨大,而且博主懒得卡常,所以只有80分。

关于[ZJOI2017]汉诺塔一题的一个问题

2019-03-06 11:34:23 By zx2003

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

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

能否予以修正? @whzzt

关于 新年的族谱树 一题的一个问题

2019-02-11 21:26:23 By zx2003

题目链接

官方题解链接

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

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

这可咋办?

uoj出bug了?

2019-02-01 14:05:08 By zx2003

【UR #14】人类补完计划的爆标做法

2018-07-09 23:18:09 By zx2003

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

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

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

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

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

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

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

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

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

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

提交记录

安利一波loj年赛hello2018

2017-12-31 17:59:19 By 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,倒数几名。

关于第284题快乐游戏鸡的疑惑

2017-05-17 22:41:30 By zx2003

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),我错在哪里?

共 11 篇博客