[CF1067E]Random Forest Rank

Link

给定一个森林,每条边有\frac 12的概率被删去,随机删掉一些边,求剩下的图的临界矩阵的秩的期望值。

Solution

满秩的矩阵的行列式不为0。结合行列式的定义|A|=\sum_{\pi_i}(-1)^{\delta(\pi_i)}\prod a_{\pi_{ij}}。对于一个行列式不为零的邻接矩阵,其必要条件是\exist \pi_i,\text{s.t.}\prod a_{\pi_{ij}}\not=0
\pi_i循环分解,循环内相邻的点都有边连接。然而,对于一个不存在环的森林,这样的循环大小只能为2——即一条边连接的两个点。因此,求出这个森林的最大匹配,设为m,那么就能选出一个大小为2m的点集,其邻接矩阵满足\exist \pi_i,\text{s.t.}\prod a_{\pi_{ij}}\not=0的条件。
另外,选出的这个点集,完美匹配是唯一的,因此,只会有一个\pi_i满足上式子。
由此,问题转化为求期望最大匹配。
然后就不会了 先坑着吧

Code

[loj 6053]简单的函数

Link

Solution

p xor 1并不是积性函数
但是除了p=2的时候,p^1=p-1
p和1都是积性函数,就可以筛出来然后加上2把p=2的情况修正好。

Code

const int P=1e9+7,inv2=500000004;

int Add(int x,int const &y) {
    return (x+=y)>=P?x-P:x;
}

int Minus(int x,int const &y) {
    return (x-=y)<0?x+P:x;
}

int Mul(long long x,int const &y) {
    return x*y%P;
}


const int N=2e5,XN=N+11;

int prime[XN],pcnt,psum[XN],fsum[XN];
void Prep() {
    static bool notPrime[XN];
    for(int i=2;i<=N;++i) {
        if(!notPrime[i])
            prime[++pcnt]=i;
        for(int j=1;j<=pcnt && i*prime[j]<=N;++j) {
            notPrime[i*prime[j]]=1;
            if(i%prime[j]==0)
                break;
        }
    }
    for(int i=1;i<=pcnt;++i)
        psum[i]=Add(psum[i-1],prime[i]);
}

int lim,psz;long long n;
struct Identifier {
    int id[2][XN],cnt;
    int &operator [](long long x) {
        int &res=x<=lim?id[0][x]:id[1][n/x];
        if(res==0)
            res=++cnt;
        return res;
    }
}id;


int F(int p,int t) {
    return p^t;
}

int g[XN*2];

int H(long long n,int m) {
    if(n<=1 || m>psz)
        return 0;
    int res=Minus(g[id[n]],fsum[m-1]);
    for(int i=m;i<=psz && (long long)prime[i]*prime[i]<=n;++i) {
        long long pt=prime[i],pt1=pt*prime[i];
        for(int t=1;pt1<=n;++t,pt=pt1,pt1*=prime[i])
            res=Add(res,Add(Mul(F(prime[i],t),H(n/pt,i+1)),F(prime[i],t+1)));
    }
    return res;
}

int main() {
    Prep();
    static long long kp[XN*2];
    int kpc=0;
    fin>>n;
    lim=sqrt(n)+0.5,psz=std::upper_bound(prime+1,prime+1+pcnt,lim)-prime;
    static int g1[XN*2],g2[XN*2];
    for(long long l=1,r;l<=n;l=r+1) {
        r=n/(n/l);
        kp[++kpc]=n/l;
        g1[id[n/l]]=Minus((n/l%P)*(n/l%P+1)%P*inv2%P,1);
        g2[id[n/l]]=Minus(n/l%P,1);
    }
    for(int j=1;j<=psz;++j)
        for(int i=1;i<=kpc && (long long)prime[j]*prime[j]<=kp[i];++i) {
            g1[id[kp[i]]]=Minus(g1[id[kp[i]]],Mul(prime[j],Minus(g1[id[kp[i]/prime[j]]],psum[j-1])));
            g2[id[kp[i]]]=Minus(g2[id[kp[i]]],Minus(g2[id[kp[i]/prime[j]]],j-1));
        }
    for(int i=1;i<=psz;++i)
        fsum[i]=Add(fsum[i-1],prime[i]^1);
    for(int i=1;i<=kpc;++i)
        g[i]=Add(Minus(g1[i],g2[i]),kp[i]>=2?2:0);
    fout<<Add(H(n,1),1)<<'\n';
    return 0;
}

[ICPC 2018 Xuzhou Online]Easy Math

Link

Solution

\sum_{i=1}^n\mu(ix)=\mu(x)\sum_{i=1}^n\mu(i)[\gcd(i,x)=1]

考虑计算

\begin{aligned}
&\sum_{i=1}^nf(i)\\
&f(i)=\mu(i)[\gcd(i,n)=1]
\end{aligned}

首先,

f(i)=\begin{cases}
1,&i=1\\
-1,&i=p{\ \rm and\ }p\not|x\\
0,&i=p^k{\ \rm or\ }p|x
\end{cases}

然后,分\gcd(i,x)的不同情况讨论,容易知道f(i)是积性函数。
因此可以使用min25筛法了。

Tips

还是不必拘泥于g的形式……

Code

const int N=5e4,XN=N+11;

int prime[XN],pcnt;
void Prep() {
    static bool notPrime[XN];
    for(int i=2;i<=N;++i) {
        if(!notPrime[i])
            prime[++pcnt]=i;
        for(int j=1;j<=pcnt && i*prime[j]<=N;++j) {
            notPrime[i*prime[j]]=1;
            if(i%prime[j]==0)
                break;
        }
    }
}

int n,lim,psz;long long x;
struct Identifier {
    int id[2][XN],cnt;
    int &operator [](int x) {
        int &res=x<=lim?id[0][x]:id[1][n/x];
        if(res==0)
            res=++cnt;
        return res;
    }
}id;

long long dv[100];int dt;
int Mu(long long x) {
    int res=1;long long cx=x;
    for(long long d=2;d*d<=cx && x!=1;++d)
        if(x%d==0) {
            x/=d;
            dv[++dt]=d;
            if(x%d==0)
                return 0;
            else
                res*=-1;
        }
    if(x!=1) {
        res*=-1;
        dv[++dt]=x;
    }
    return res;
}

int F(int p,int t) {
    return t==1 && x%p?-1:0;
}

int g[XN*2],fsum[XN];

long long H(int n,int m) {
    if(n<=1 || m>psz)
        return 0;
    long long res=g[id[n]]-fsum[m-1];
    for(int i=m;i<=psz && prime[i]*prime[i]<=n;++i) {
        long long pt=prime[i],pt1=pt*prime[i];
        for(int t=1;pt1<=n;++t,pt=pt1,pt1*=prime[i])
            res+=F(prime[i],t)*H(n/pt,i+1)+F(prime[i],t+1);
    }
    return res;
}

int main() {
    Prep();
    static int kp[XN*2],kpc;
    fin>>n>>x;
    int mun=Mu(x);
    if(mun==0)
        fout<<0<<'\n';
    else {
        lim=sqrt(n)+0.5,psz=std::upper_bound(prime+1,prime+1+pcnt,lim)-prime;
        for(int l=1,r;l<=n;l=r+1) {
            r=n/(n/l);
            g[id[kp[++kpc]=n/l]]=n/l-1;
        }
        for(int j=1;j<=psz;++j)
            for(int i=1;i<=kpc && prime[j]*prime[j]<=kp[i];++i)
                g[id[kp[i]]]-=g[id[kp[i]/prime[j]]]-(j-1);//(1-(j-Count(j)));
        for(int i=1;i<=psz;++i)
            fsum[i]=fsum[i-1]+F(prime[i],1);
        for(int i=1;i<=kpc;++i)
            g[i]=std::upper_bound(dv+1,dv+1+dt,kp[i])-dv-1-g[i];
        fout<<mun*(H(n,1)+1)<<'\n';
    }
    return 0;
}

SPOJ DIVCNTK

Link

Solution

使用min_25筛
由于求h的过程都只会用到[\frac ni]集合中的点,那么求g的过程中把[\frac ni]构成的集合求出来,对于这个集合的所有点分层递推(递推过程中需要用到的g也属于[\frac ni]集合),就可以求出g(i,|P|)
然后递归求h,并不需要记忆化。边界见代码。

Code

typedef unsigned long long qword;

const int N=2e5,XN=N+11;

int prime[XN],pcnt;
void Prep() {
    static bool notPrime[XN];
    for(int i=2;i<=N;++i) {
        if(!notPrime[i])
            prime[++pcnt]=i;
        for(int j=1;j<=pcnt && i*prime[j]<=N;++j) {
            notPrime[i*prime[j]]=1;
            if(i%prime[j]==0)
                break;
        }
    }
}

long long n,k;
int lim,psz;

struct Identifier {
    int id[2][XN*2],cnt;
    int &operator [](long long x) {
        int &res=x<=lim?id[0][x]:id[1][n/x];
        if(res==0)
            res=++cnt;
        return res;
    }
}id;

qword g[XN*2];

qword H(long long n,int m) {
    if(n<=1 || m>psz)
        return 0;
    qword res=(k+1)*(g[id[n]]-m+1);
    for(int i=m;i<=psz && (long long)prime[i]*prime[i]<=n;++i) {
        long long pt=prime[i];
        for(int t=1;pt*prime[i]<=n;++t,pt*=prime[i])
            res+=H(n/pt,i+1)*(k*t+1)+(k*(t+1)+1);//id[n/pt]
    }
    return res;
}

void Work() {
    lim=sqrt(n)+0.5;
    id.cnt=0;
    for(int i=0;i<=lim;++i)
        id.id[0][i]=id.id[1][i]=0;
    psz=std::lower_bound(prime+1,prime+1+pcnt,lim)-prime;
    static long long kp[XN*2];int kpc=0;
    for(long long l=1,r;l<=n;l=r+1) {
        r=n/(n/l);
        g[id[kp[++kpc]=n/l]]=n/l-1;
    }
    for(int j=1;j<=psz;++j)
        for(int i=1;i<=kpc && (long long)prime[j]*prime[j]<=kp[i];++i)
            g[id[kp[i]]]-=g[id[kp[i]/prime[j]]]-(j-1);
    std::cout<<H(n,1)+1<<'\n';
}

int main() {
    Prep();
    int T;fin>>T;
    while(T--) {
        fin>>n>>k;
        Work();
    }
    return 0;
}

胡扯min_25筛

记质数集合为P

Problem

以低于线性的复杂度求一类积性函数的和,函数需满足
f(p),f(p^k)(p\in P)很好求。

Solution

{\rm Min}(x)x的最小质因子。

g

g(n,i)=\sum f(x)[ {x\le n {\ \rm and\ } (x \in P {\ \rm or\ } {\rm Min}(x)>P_i) } ]
n < P_i^2时,g(n,i)=g(n,i-1),因为最小的{\rm Min}(x)= P_i的合数就是P_i^2
否则,考虑从g(n,i-1)中减去{\rm Min}(x)= P_i的合数的贡献,也就是\sum f(x)[{x\le n,{\rm Min}(x)=P_i}],提出f(P_i),式子变成了f(P_i)(g([\frac n{P_i}],i-1)-\sum_{j=1}^{i-1}f(P_j))
\therefore
g(n,i)= \begin{cases} g(n,i-1)&,n < P_i^2\\ g(n,i-1)-f(P_i)(g([\frac n{P_i}],i-1)-\sum_{j=1}^{i-1}f(P_j))&,\text{otherwise} \end{cases}

h

h(n,i)=\sum_{j=1}^nf(j)[{\rm Min}(j)\ge P_i]
对于h(n,i)n以内质数的贡献是g(n,|P|)-\sum_{j=1}^{i-1}f(P_j)
现在考虑合数的贡献。
枚举合数的最小质因子P_j,那么最小质因子为P_j的合数的贡献就是\sum_{t\ge 1,P_j^{t+1}\le n}(h([\frac n{P_j^t}],j+1)f(P_j^t)+f(P_j^{t+1}))
因此
h(n,i)=g(n,|P|)-\sum_{j=1}^{i-1}f(P_j)+\sum_{j\ge i}\sum_{t\ge 1,P_j^{t+1}\le n}(h([\frac n{P_j^t}],j+1)f(P_j^t)+f(P_j^{t+1}))
答案就是h(n,1)了。

Tips

具体实现的时候,g不一定求\sum f(x)[ {x\le n {\ \rm and\ } (x \in P {\ \rm or\ } {\rm Min}(x)>P_i) } ],求出的g只要能使得上式可以被很快求出即可。

CCPC2018桂林站游记


选桂林是为了旅游,总体来说,除了没去阳朔有点遗憾以外,旅游得挺不错,而至于比赛嘛,emmmmmm

day -1

沈阳站回来以后一直在咸鱼,不知不觉就混到了周五,该走了。
坐着阿訇叫的七座商务很顺利地到了机场。而在过安检的时候,SR的登机牌名字打的重叠了,折腾了一会才过了安检。
过了安检之后,SR帮我用京东支付买了一瓶饮料,结果他想起来他并没有在京东支付上绑定银行卡,结果仔细一看,原来上一个用他的手机号的人用这个号注册了jd,然后又绑定了银行卡,又开通了短信验证码支付,于是乎SR就可以不费吹灰之力地随便刷。这个号码的上一个主人还真是大意……而且在他的京东账号里并没有手机号等联系方式,只有收货地址。打算写封信告知一下2333

飞机餐不大好吃……不过也没抱多大期望。飞机落地之后,一个中年男子来问我们是不是参加程序设计竞赛的,我们很惊奇……然后他热情地自我介绍,并且给我们每人发了一张名片,原来他是机械工业出版社的编辑人员。想起我们书包里一本本厚厚的黑色的书,瞬间产生了很亲切的感觉~
穿着毛衣上的飞机,一下飞机,立马热成狗。从北飞到南就像穿越了时间……到酒店换上夏装之后,我们就出去玩啦~

我们住的地方离象山很近,SR和阿嘤队打车去,我和PY骑车去。街头充满着桂花香,还真是很久没有闻到过了。好感++
象山景区挺小的,登山的台阶很陡峭,但是山并不高。在象山最高点有个观景台,而从观景台望下去,视野里充满了煞风景的小房子。不过这也不是个专门的旅游度假区,也是没办法的吧……
在象山的观景台可以看到东边的群山,和我印象中北方的远山的轮廓大不相同。那些山都是奇形怪状,出来的轮廓也是充满了导数剧烈变化的点。盯着远山看了一会,就下山了。

出了景区之后,我们去追随阿嘤队吃吃吃。他们先去吃了一家米粉,然后去了一家烧鹅店。我们就也去了一家米粉店,尝了尝传说中的桂林米粉,真的挺好吃。米粉口感很嫩,配的那些小菜,酸豆角之类的也符合我的口味,很不错。在桂林前前后后我大概吃了七八碗米粉吧……
然后烧鹅店。烧鹅也挺好,皮很酥脆,但是肉质比北京烤鸭嫩很多。不过我最后还是没尝出来啤酒鱼有什么啤酒味……整体来说,吃吃吃的方面,比沈阳站全程M记好多了。

吃完之后,又去了日月双塔公园,登上去看了看;然后去了个步行街,什么都没消费……回到了宾馆。

day 0

七点半起,想等人一起吃饭,饿着肚子等了一个小时才和阿訇、PY去吃早饭。

快到中午的时候,我们去了桂电。
桂电的校名应该是中石题写的。学校挺旧挺小,和小破邮本部挺像的。而食堂的饭实在是说不上好吃,于是我们把剩下的饭票全都换成了果汁。15元的饭票,换2.5元的果汁,食堂的这笔帐真是爆赚。
在食堂遇到了南老师、汪神、晨神和可爱的佳蔚哥哥姐姐。没选上南京站真是挺遗憾的,如果能去南京站的话就能遇见Menci、牛神、恒妹了。

直接翘掉了开幕式,去了比赛现场。硬件一切正常,然而我们对面坐着一支pku队,背后一支hust队,蒟蒻瑟瑟发抖。
试机赛的提米比较奇怪,沈阳站放了三道签到题,而这场放了一道签到,一道挺难的期望,一道挺难写的模拟,一道挺奇怪的猜结论乱搞题。一开始读错了期望题,和SR自闭了一会,发现样例都过不了,于是扔掉之后分头开搞。乱搞题由SR带病做,猜了个奇怪的结论交上就过了。签到题我粘了最大流模板过了。此时还有半个小时结束,貌似唯一可过的就是写简单的python解释器那道模拟题。
我写完了表达式求值以外的部分,发现不会表达式求值。PY也只有模糊的一点印象…被一道初学栈的标准例题卡住,真是丢人呢……

试机赛结束,SR、yjz和gzz、Yousiki出去愉快地玩耍,PY和jiangshibiao等一众绍一同学出去愉快地玩耍,扔下弱省弱校的我孓然一身……在学校里逗留一会,发现我打不上车,只好提着换出来的一袋子果汁、背着词典走回了宾馆……桂花香真好闻++

晚上想再看看表达式求值,竟看不懂。想想第二天也不可能考,就大胆地扔下不管了。

day 1

早晨还是很凉快的。
开场秒了G,想抢一血,写完直接交,结果WA了。改了几个地方交了几次还是不行,就把电脑让给SR写D,然后和PY对着代码自闭。SR的D过掉之后,我又改了下还是WA。最后SR想了想指出了我的想法的问题:应该枚举差分数组gcd的所有质因子,然后依次看看调整到各个质因子的整数倍需要多少次操作。改完之后总算过了。签到题-4,好大一口锅……
然后就跟榜写H、J。H的想法比较简单,我和SR大体统一一下他就去写了,结果过不掉。此时我和PY对着J自闭,我猜了个结论,然后他接着猜了个结论,感觉靠谱,他就去写了,过掉了。
H题本来的写法比复杂,讨论的情况较多。我灵机一动,发现可以直接从’a’无脑枚举到’z’依次判断也并不会超时,写一发,代码也很短,直接就过了。后来得知阿嘤队这道题代码接近100行……
H过掉之后一起对着A自闭。。。感觉A过的人挺多的,但是不知道自闭了多久,也没有进展……此时有人过了L,发现是个计算几何讨论题。SR大力讨论了一发,然后让我去写了。我写的同时他们对着C自闭。
这个计算几何并不涉及什么特别的算法,就是简单的一些操作组合组合,不过写完之后还是挺长的。然而WA了一发,于是把电脑让给SR让他写C。
SR对C的推进也不怎么顺利,我对着代码找了一会错误之后,改了点东西,还是过不了。我又着重考虑了边界情况,抽出来几种单独判掉,终于A了。此时已经封榜,离结束还有大约50min。
SR继续搞C,我也和他们一起看题意,听听做法感觉还挺靠谱的,但是写完之后就是过不了。我们三个一起想办法X掉这个做法,叉叉改改,改了又叉,而最后想到的改法需要线段树,已经没时间写了。于是随机胡交了十几发,比赛结束了。

感觉这次应该比较稳,但是还是心里有点虚。最后结果一出,我们rk31,如果罚时少点就能Au了……

总结

这场发挥的还可以吧,这个排名感觉也比较符合场上的状态。现在主要的问题就是中后期的推进,这还需要好好训练,提升水平,才可能过掉难题,过掉金牌题。


ICPC2018沈阳站游记

只能选两站,怀着去旅游的心理选了桂林,然后无脑跟阿嘤队选了沈阳。当时没发现两站是连着的……

day -x

闲下来的时候就是准备模板,重学了一些好东西,但是没做多少题。感觉脑袋变得不太灵光了。
队伍集体训练几乎没有,唯一一次是vp了2017沈阳站,结果我clone的比赛是从uva上拉的,没数据,一交就过……花五个小时打了场假比赛。

day 0

高铁八点发车,得五点半从村里出发。我们早早下去,在甲子钟冻得瑟瑟发抖。
结果褚大哥睡过了??
结果阿嘤他们楼的宿管大妈失踪了??
奔跑的阿嘤队↓

走到沙河站,腿都冻麻了。。

换了换座位和阿嘤队坐一起,大约十二点到的沈阳,一路扯扯皮很快就过去了。
出站之后打车去酒店,在沈阳打车好便宜!!
在某家M记吃午饭,一位店员大妈对我们说:麦当劳就愿意招你们东北大学的学生,因为你们素质很高!我们没敢承认我们其实是素质低的北邮学生O_O
发的参赛服在淘宝上可以搜到

感觉太蠢于是就无视规定没穿,结果就是我们只得在观众席上观看开幕式……快结束了才把我们放进去打热身赛。
热身赛三道题,一人切一题,很快写完了。每个人都写了一会儿代码,适应一下键盘,总体感觉海星。
热身赛前刚刚发的饭票,打完之后就被SR弄丢了。找了好几个志愿者,最终终于又要到了一份。中间遇到了一个志愿者,给我们留下了很大的心理阴影。
“你们哪个学校的?”
“北邮的。”
“北邮儿的?”(表情突变)
“大几的?”
“大一的。”
“北邮曾经给了我很大的伤痛。”
“那有个你们大二的学姐。”
本以为他和北邮怎么苦大仇深,听到这的我一脸黑线==

学校准备的自助还是很好吃哒哒哒~

本来立下flag,此生不碰2-sat。结果没有2-sat板子,不得已又看了一眼。结果发现我在考场上离正解只差三行代码,顿时感觉十分难受。

睡不好

day 1

睡不好

将头发梳成大人模样,穿上一身帅气夕阳红老年装。
M记里基本全都是ACMer。

九点钟,比赛开始了。
题面都很长,我找了一道题面看起来最短的C题开始读题,题意还是比较好理解的,就是将前k个数字冒泡排序之后序列的LCS\ge n-11…n的排列个数。我一开始考虑按照排序之后不在LCS里面的那个元素的大小与k的关系和位置是否在前k个分类,每种分类写出一个式子来算一算发现不对。后来发现四种情况中有两种情况会出现重叠,想了想发现没什么办法,就扔给SR跑路了。
与此同时,PY跟榜切掉了签到题,因为把==写成=查了很长时间(初学者*1)

SR拿着我的式子改,我写暴力让他找规律,最后找到了规律,开始写。写完之后WA了。原因是没加Cases#。加上之后WA*2,原因是n==k的情况是特判输出的,那里每加Cases。改完之后WA*3,我又看了看题目发现k可能>n,于是把特判的条件改了改,终于过了(初学者*2)。

当时我们rk30左右,寻找下一个突破口。
SR之前看的n\le 10^{18}的约瑟夫问题,满足\sum\min(步长,步数)\le 10^6,我和PY拿过来,翻开白书和具体数学,结合经典问题的递推思路开始想,但并没有什么结果。
PY又读了一道维护平面内满足到某个点欧式距离为给定值的整点的题目,貌似暴力可搞,我打个表发现所有完全平方数至多有一组平方和的划分方法,于是就写。写完之后TLE。原因是1000组数据每次memset大数组(初学者*3)。改成时间戳之后WA,发现时间戳写错了(初学者*4)。改完之后还是WA,发现打表的时候内层循环把i++写成j++,出来了错误的结论(初学者*5)。不过好在改过来之后所有数字总的划分数不多,于是就改成用vector存每个数字的两个平方数的划分方案。终于过了。
此时又从rk80+回到了rk30+,但是由于罚时爆炸,三题垫底。此时还有不到两个小时。

封榜前没再写题,第一次感受到离开手机查词之后的无助。词汇量太小,而翻词典翻的太慢,被各种卡题意。最后掉到了rk45,感觉这个罚时,很虚。

封榜后全队一起约瑟夫希望保住一块Ag,SR想出了一种挺靠谱的方法,是一种细节多的让人lao kuo teng的方法,按照我的理解,在50min内写完并且A掉是比较难的。但是孤注一掷,就让SR写吧。我和PY在一边双排自闭。在一旁看题,也没有想出哪道题有什么好写的方法。到最后SR写不完了,我们三个在悲伤中自闭完了剩下的十分钟。

比赛结束之后,我们不想看滚榜,打算直接去找家火锅店狂吃一通发泄一下。看着封榜后后面队伍的交题记录,我已经做好打铁的准备了…然而还没找到火锅店,fqk告诉我们卡线Ag了…

月加队打的很自闭,和我们一起卡线Ag了…

阿嘤队封榜之后也没过题,最后还是一个Ag…

总结

说实话,这块Ag真是给我一种白捞的感觉。。打成这样,各种初学者的低级错误。。只能感谢各位轻虐了…
和外校交流发现我们队训练少的可怜,像中大南大,并不能签到NOI比较靠前的选手,但是上大学以后刻苦训练最后能和清北叫板。等桂林打完,这个慌忙的赛季结束,该好好想想以后的路怎么走了。

[hdu6223][Shenyang Onsite 2017]Infinite Fraction Path

Link

每个点有一个出边,每个点上有一个字符。求字典序最大的长度为n的路径。

Solution

广义后缀数组!预处理一下一个点往后跳2^i步到的点,然后魔改一下后缀数组就好了。

Code

const int XN=150000+11,XLOGN=18;

int par[XN][XLOGN];
char v[XN];
void Work() {
    int n;fin>>n>>(v+1);
    for(int i=1;i<=n;++i)
        par[i][0]=((long long)(i-1)*(i-1)+1)%n+1;
    for(int b=1;(1<<b)<=n;++b)
        for(int i=1;i<=n;++i)
            par[i][b]=par[par[i][b-1]][b-1];
    static int temp[2][XN],cnt[XN],*x=temp[0],*y=temp[1],sa[XN];
    int m=256;
    std::fill(cnt+1,cnt+1+m,0);
    for(int i=1;i<=n;++i)
        cnt[x[i]=v[i]]++;
    std::partial_sum(cnt+1,cnt+1+m,cnt+1);
    for(int i=1;i<=n;++i)
        sa[cnt[x[i]]--]=i;
    for(int b=0;(1<<b)<n;++b) {
        std::fill(cnt+1,cnt+1+m,0);
        for(int i=1;i<=n;++i)
            cnt[x[par[i][b]]]++;
        std::partial_sum(cnt+1,cnt+1+m,cnt+1);
        for(int i=1;i<=n;++i)
            y[cnt[x[par[i][b]]]--]=i;
        std::fill(cnt+1,cnt+1+m,0);
        for(int i=1;i<=n;++i)
            cnt[x[i]]++;
        std::partial_sum(cnt+1,cnt+1+m,cnt+1);
        for(int i=n;i>=1;--i)
            sa[cnt[x[y[i]]]--]=y[i];
        std::swap(x,y);
        int p=x[sa[1]]=1;
        for(int i=2;i<=n;++i)
            x[sa[i]]=y[sa[i-1]]==y[sa[i]] && y[par[sa[i-1]][b]]==y[par[sa[i]][b]]?p:++p;
        if((m=p)==n)
            break;
    }

    for(int i=1,p=sa[n];i<=n;++i,p=par[p][0])
        fout<<v[p];
    fout<<'\n';
}

int main() {
    int T;fin>>T;
    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d: ",ks);
        Work();
    }
    return 0;
}

O(n)求字符串的最小表示

Problem

求一个字符串的循环移位中字典序最小的那个。

Solution

两个指针指向两个同构串的开头,比较它们的大小,较大的那个串的与另一个串相等的那一部分及其第一个不同的字符不可能是最小同构串开头,可以直接跳过。

Code

int MinimumRepresentation(int *a,int n) {
    ++a;
    int p1=0,p2=1,len=0;
    while(p1<n && p2<n && len<n) {
        if(a[(p1+len)%n]==a[(p2+len)%n])
            len++;
        else {
            (a[(p1+len)%n]>a[(p2+len)%n]?p1:p2)+=len+1;
            if(p1==p2)
                p2++;
            len=0;
        }
    }
    return std::min(p1,p2)+1;
}