魔法の庭園、私たちが一緒に暮らす楽園

A magical garden!We're lived here.

0%

置顶 | 发表于 更新于 分类于
本文字数： 101 阅读时长 ≈ 1 分钟

重大更新日志

Legend(25.10.01~25.10.09)

  • 25.10.01 建站完成。
  • 25.10.09 进行博客美化。

Lumina(25.10.10~?)

ep.Start

  • 25.10.10 第一篇博文发布。

发表于 分类于 ， ， ， ，
本文字数： 667 阅读时长 ≈ 1 分钟

这是一篇 Pólya 题解。若想了解 DGF（狄利克雷生成函数）做法请移步。

本质不同问题+染色一般用 Pólya 定理解决。

在考虑环形问题之前（即用 Pólya 定理之前），先考虑链状问题，即所有元素排列成链状时，显然可以设计如下的转移状态：fi, j 表示长度为 j，元素乘积为 i 的方案数。转移就大家各显神通吧。官方题解给出了 Θ(Ulog2U) 的转移（实际上只有改变维度顺序，但是足以比暴力转移优化掉一个 log ）。但是我用 Θ(Ulog3U) 不要脑袋暴力转移不加任何优化过了有些好笑。

算了还是讲讲吧。考虑序列一个一个加元素，那么第二维 j 可以先行枚举。第一维转移显然是调和级数，所以复杂度是 Θ(Ulog2U)。比起 3log  做法本质区别是改变维度遍历顺序，使得不需要考虑位置的优化。当然两种方法得出来的结果是相同的。

接下来是迁移到环上问题。我们重新复习一下 Pólya 定理：

给定群 G 在集合 X 上的作用和颜色集合 C，则不同的染色方案的数目 $$ |C^X/G|=\frac{1}{G}\sum_{g\in G}m^{c(g)} $$ 这里，m 是颜色数目，c(g) 是元素 g ∈ G 的置换表示的轮换分解中的轮换数目。

这里颜色集合比较显然，CX 即线性问题的所有染色方案，G 则是所有的环移动方案，即： r0, r1, …, rj − 1 这里的 j 即我们枚举的环长。那么关键是这里的 c(g)。对于 rk 对应的 g，令 d = gcd (j, k)，那么有 $c(g_{r_k})=f_{\sqrt[\frac{j}{d}]{i},d}$。这个转移式是 Θ(Ulog2U) 的。那么我们就得到一个 Θ(Ulog2U) 的做法了。

发表于 分类于 ， ， ， ，
本文字数： 1.5k 阅读时长 ≈ 1 分钟

难度：2073

似乎全用线段树+二分写的。不过这种方法确实比较直接。这里提供一种实现也许更加简单的方法，单调栈+二分。

发现实际上我们拥有了 w 数组之后，要掌握所有的区间信息只需要找到一些 拐点。这里 拐点 的意思即对应 1 操作和 2 操作。在平面上两个操作相当于把一段前缀区间分别全部向左和向右靠拢，而靠拢的位置即给出的 v 就是我们要维护的 拐点。

然后我们会发现，维护的拐点若按照区间大小降序排序，有可能会出现“……左，左……”或”……右，右……“的情况，此时只需要保留最大区间所代表拐点即可，其他都可以删去。也就是实际上我们要维护的拐点按照区间大小降序排序必然形如“左，右，左，右……“交替循环下去。那么这个东西+修改可以用一个单调栈维护。每次查询的时候找到包含最小的拐点，然后在拐点二分就好。有一些实现上的细节（如数值处理细节）会在代码中标注。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
int n,q,w[N],sta[N],top,pos[N];
bool check(int p,int x){// 判断点 x+0.5 是否在拐点 p 内
    if(p&1)return pos[p]<=x&&x<pos[p]+w[sta[p]];
    return pos[p]-w[sta[p]]<=x&&x<pos[p];
}
int query(int x){// 查询
    int l=1,r=top,res=1;
    while(l<=r){// 二分 1 - 拐点
        int mid=(l+r)/2;
        if(check(mid,x))res=mid,l=mid+1;
        else r=mid-1;
    }
    int p=sta[res];
    if(res&1)x-=pos[res];// 翻转区间
    else x=pos[res]-(x+1);
    l=1,r=p,res=p;
    while(l<=r){// 二分 2 - 拐点内具体编号
        int mid=(l+r)/2;
        if(x<w[mid])res=mid,r=mid-1;
        else l=mid+1;
    }
    return res;
}
int main(){
    n=read();
    REP(i,1,n)w[i]=read();w[n+1]=inf;// 添加 n+1 号点方便处理
    sta[++top]=n+1,pos[top]=0;// 这里 sta 维护拐点区间标号，pos 维护拐点位置
    // 第一个默认左拐点
    q=read();
    REP(i,1,q){
        int type=read(),x=read();
        if(type==1){
            while(x>=sta[top])--top;// 遇到之前较小区间拐点直接删掉，下同
            if(top%2==0)sta[++top]=x,pos[top]=pos[top-1]-w[x];// 注意要保持“左，右，……”的形态
        }else if(type==2){
            while(x>=sta[top])--top;
            if(top%2==1)sta[++top]=x,pos[top]=pos[top-1]+w[x];
        }else if(type==3)write(n+1-query(x)),putchar('\n');// 注意 query 求的是编号，而答案时后缀长度
    }
    return 0;
}

发表于 更新于 分类于 ， ，
本文字数： 246 阅读时长 ≈ 1 分钟

10.15

最近一段时间复健算法。打了一场 ARC 和 Luogu 的一场 ICPC 区域赛镜像赛。虽然打的不是太理想，但是至少稍微熟练了一些。

昨天晚上入坑原神。从此我再也不是只打音游的音游吃了哈哈哈。

10.18

CCPC 区域赛镜像赛？感觉比上场镜像赛简单一些。然而一万年没打算法竞赛还是完蛋了。

好像从初中以来就经常会深夜 emo 耶。介么肥事捏？

嗯嗯嗯这启示了我们不能吃夜宵，要早睡早起（

今天上午应该会大概计划一下接下来的时间规划以及补一补前两场的题和 sol。敬请期待。但是我缺的计算几何这一块谁给我补啊（哭）

发表于 更新于 分类于 ， ，
本文字数： 108 阅读时长 ≈ 1 分钟

流明(Lumina)

我们总是期待着晨曦的到来，在茫茫黑夜当中。

撕扯着，

叫喊着，

向着这最后的一点微光发出绝命的冲刺。

无数的人呐喊。

无数的人湮没。

“为了最后的一点光，你们值得吗？”

“只要是为了最后的流明而战，死又何惧？”

发表于 更新于 分类于 ， ，
本文字数： 216 阅读时长 ≈ 1 分钟

New Step!!!

这一切是往事不堪回首的终点，亦是全新起航的起点！

建完博客网站发布的第一篇博文！

这里是一个 18 岁小女孩的博客。喜欢算法，电子音乐；偶尔打打音乐游戏；正在学习英语和日语（想去秋叶原了说是）。兴趣为上。

梦的起点。我将会在这上面发布一些算法学习过程，电子音乐鉴赏及制作，音游游玩经历，以及一些个人的生活记录。欢迎来到偶的博客的各位友友们。

虽然是第一篇按道理应该说的多一些的，但是碍于我拙劣的文笔，就暂且提这一些叭。

拜拜。