为了去隔壁给 talk，不得不又重温了本作 = =。

• 游戏说 99：我只负责调酒，不负责拯救世界

我觉得要是游戏也和隔壁 NeurIPS 一样，发时间检验奖（Test-of-Time Award）的话，一个评判标准我觉得大概得是这个游戏是否引领了很多 xxx-like，那按照这个标准 rogue 是必然能上榜的，《银河战士》和《恶魔城月下夜想曲》大概也能的！

在调研了一番之后，很神奇的是我觉得《赛博行动酒保行动》后续也有很多酒保行动-like 的！

首先我觉得本作的设计在一个 game jam 体量的作品里还是非常特别的！你说它是模拟经营吧，不能说没有但是怎么看也不如今年爆红的《沙威玛传奇》，这个游戏绝对是 AI 游戏的代表作了，哈哈玩法我觉得是那种经典古早 flash 游戏，最后一看人家作者还真写 flash（什么，《沙威玛传奇》都能玩出竞速模式吗？）。

你说它是 galgame 吧，hmmm，它居然连对话选项都没有，但分支剧情又都是通过调酒玩法和经营的分数去触发的，这点又类似《仙剑客栈》那样的传统模拟经营了。

我觉得整体氛围最接近显然是 Coffee Talk 系列，虽然背景设定类似《奥秘：蒸汽与魔法》那样有点偏奇幻。

然后同样赛博朋克世界观下的有《红弦俱乐部》以及之前在游机会玩到的《爱&机器人维修技术》。

居然还有这么多联动。。。
– 如何评价少女前线与VA-11 Hall-A赛博朋克酒保行动的联动活动？
– 赛博朋克酒保行动和赛博朋克红究竟联动了啥？（特别节目）【夜之城求生指南】

由于最近在填坑，所以刚好记录一下剧情。

（剧透警告!）

剧情

首先感觉两部的核心除了尼克和朱迪这一对 cp 的性格和阵营上的冲突，还有一个是如何维护 Zootopia 的 DEI（尽管这好像是一个被用坏掉了的词），第一部是肉食动物与草食动物之间，第二部则是哺乳动物和爬行动物之间。

故事开场利用了一场马里奥赛车一样的追逐戏快速的让我进入了状态，并且通过留下的蛇皮也制造了十足的悬念。使得我开始期待一个梅兰妮或是神偷卡门那样的展开，可结果光速发生第一次剧情上的反转，此时朱迪和尼克的阵营上的冲突也开始显现，尼克作为混乱中立显然不想掺和进去，而朱迪作为守序善良自然要贯彻自己 make the world a better place 的信念自然不惜深入险境。

不过我这里感觉是这个翻转比隔壁阿兹卡班的囚徒还要快，凭借蛇蛇的一面之词朱迪的立场就光速翻转，还险些害死了 Chief Bogo！接下来就进入死亡圣器的逃亡环节，朱迪像 cyberpunk 2077 里流浪者阵营一样开始了大逃亡，经过一个神似长弓溪谷坠机之地的水上集市（但是人很多）的地方之后，来到了一个有点像元组星球大战那样的地下酒吧，然后莫名其妙任务道具就丢了。中间一段踩河马脑袋的演出真的就像这类3D平台跳跃游戏的解谜一样，前面甚至还有铺垫的，你肯定在奥德赛 or 古惑狼里遇到过类似的关卡。

钻管子的演出也让人感觉有点梦回超级马里奥大电影。然后尼克就被抓了，说实话我要是朱迪这个时候我肯定已经后悔自责的要死了，第一要务肯定是去救尼克，而不是信任这个蛇蛇。不过尼克遇到了神仙队友居然这么轻易的就越狱成功了。

话说这只竹叶青居然叫 garry，ib 里的 garry 也恰好代表色是蓝色。

然后第二波翻转我方小队里迅速的出现了一个内鬼，说实话我一开始还以为蛇蛇和这个猞猁是 cp 关系，然后上演一场出类似隔壁叙拉古人那样对家族的反抗的剧情，结果居然跳反了？不过这期反派实在战斗力不太行，被有惊无险的光速击败了。

女性主义

回来的路上 m200 说到，尼克在本作不就是一般意义上的女主位置么。确实，不过这种创作手法也不是第一次见到了，最经典的例子可能就是《空之轨迹FC》里的艾丝蒂尔和约修亚了吧。然后尼克本作完全就是宠妻狂魔，朱迪感觉完全就像是少根筋的直男似的，拜托我都没你这么焦虑！也就是你是迪士尼童话故事的主角不然感觉中间我们都死好几次了都。

• 逗比的预言家，这款19年前的游戏为何能一战成名？带你笑着看完神作《空之轨迹》
• 游戏说 27：电子游戏与性别歧视

上面这个视频居然没提到寄生前夜的女主 Aya，她可是我小时候玩过的觉得印象最深刻的女主角了，可能原因之一是她除了要和 boss 作战，还要面对来自身体内部线粒体内部的对抗与挣扎。

总之我觉得本作无论是对女性主义，对 DEI，对刻板印象的反击（神话、寓言故事里蛇通常是邪恶的）都处理的非常自然，感觉比《冰雪奇缘》还要棒！（除了没有女同）

先把所有数都减一，n 表示进行了 n 个回合。

设 E[i] 为最后 i 出现的期望次数。那么显然 E[n] 最容易求，就是每次都 p，E[0] 也容易求，每个回合的 delta 只与当前有多少个 0 有关，看起来可以递推。
E[n-1] 则需要讨论一下，E[n-2] 就更要讨论了。

仔细观察，我们发现不得不枚举第一次出现 i 的时刻，设 A[i][j] 等于 i 第一次出现在 j 时刻的概率，我们有：

E[i] = A[i][j] B[n-j] | j = 0..n

这里 B[i] 表示当前最高位后续再进行 i 个回合期望出现多少次，和求 E[0] 类似，这个值只与后续进行的回合数有关！

进一步，考察 A[i][j]，最后第 j 时刻必然是 p 事件，前面二项分布即可：

A[i][j] = C(j-1, i-1) p^i (1-p)^(j-i)

考察 B[i] 有：

B[0] = 1
B[i] = B[i-1] + B[i-1] / n-i

于是可以得到暴力 O(n2) dp。

#include <lastweapon/io>
#include <lastweapon/number>
using namespace lastweapon;

const int N = 1009;
Int Fact[N], iFact[N];
Int E[N], A[N], B[N];
int n, p, q;

Int Binom(int n, int m) {
    if (m < 0 || m > n) return 0;
    return Fact[n] * iFact[m] * iFact[n-m];
}

int main(){
    MOD = 998244353; RD(n, p); p = Int(p) / 100; q = Int(1) - p;
    Fact[0] = 1; REP_1(i, n) Fact[i] = Fact[i-1] * i;
    iFact[n] = _I(Fact[n]); DWN_1(i, n, 1) iFact[i-1] = iFact[i] * i;
    B[0] = 1; FOR(i, 1, n) B[i] = B[i-1] * (q+n-i) / (n-i);

<pre><code>E[0] = B[n-1]; FOR(i, 1, n) {
    FOR(j, i, n) E[i] += Binom(j-1, i-1) * pow(p, i) * pow(q, j-i) * B[n-1-j];
}

REP(i, n) printf(&amp;quot;%d\n&amp;quot;, E[i]);
</code></pre>

}

再卷积即可。

题意：次小素因子前缀和。

类似 PE 521 求最小素因子前缀和，虽然不是积性函数，但不妨碍我们筛。

令 S(n, k) 表示次小质因子 >= P[k] 时的前缀和（P[0] = 0)。
转移，分两种情况：
1. 剩余部分是一个更大的素数，贡献是，p * (g[id(n)] – g[p])。
2. 枚举最小因子分解，递归。

#include <lastweapon/io>
using namespace std;

const int N = int(1e6) + 9;
LL n; int nn; int P[N], Pn;
LL di[N], g[N]; int dn;
inline int id(LL x) {return x <= nn ? x : dn-n/x+1;}

LL S(LL n, int k) {
    int p = P[k]; if (n <= p) return 0;
    LL z = p * (g[id(n)] - g[p]);
    FOR_1(i, k+1, Pn) {
        LL p = P[i]; if (p*p > n) break;
        for (LL j=n/p;j>=p;j/=p) {
            z += S(j, i) + p;
        }
    }
    return z;
}

LL S(LL n) {
    ::n = n; nn = sqrt(n); Pn = dn = 0;
    for (LL i=1,j;i<=n;i=j+1) {
        di[++dn] = j = n/(n/i);
        g[dn] = j-1;
    }
    FOR_1(p, 2, nn) if (g[p] != g[p-1]) {
        P[++Pn] = p; for (LL i=dn,ii=di[i];(LL)p*p<=ii;ii=di[--i]) {
            g[i] -= g[id(ii/p)] - g[p-1];
        }
    }
    if (!Pn) return 0;
    return S(n, 0);
}

int main(){
    LL l, r; RD(l, r);
    cout << S(r) - S(l-1) << endl;
}

• https://uoj.ac/problem/164

Kimi 居然会做这个题的暴力 https://kimi.moonshot.cn/share/cvaqfgsjc3febjghkqh0，
除了一些细节问题（欧姆定律和电阻公式实际不需要，要开 long long），实际能拿 40 分！

然后注意到本题的这个区间减操作，是不能减成负值的（AI 居然也能注意到？），所以我们还需要支持区间最值操作，而区间赋值操作是可以用区间最值模拟的，具体说来我们需要维护一个双半群，标记合并是：

struct F{LL a0, b0, a1, b1;};
F comp(F r, F l) {
    return F{
        max(l.a0+r.a0,-INFF),
        max(l.b0+r.a0, r.b0),
        max(l.a1,l.a0+r.a1),
        max(l.b1,l.b0+r.a1,r.b1)
    };
}

注意这里历史标记需要当前标记的信息来维护，所以不能开两个线段树分别维护。

https://uoj.ac/submission/745579

• Codeforces, The history of some recurring problem
• Luogu P6292 区间本质不同子串个数
• https://uoj.ac/problem/608
• https://www.fzoi.top/problem/4449

初见杀，实际套路，应该放一起做！

首先能离线当然考虑离线（Ukkonen 可以魔改支持左删，但是好像还是不能很好的支持左加和右删，否则我们甚至能莫队？），
那么我们只要维护一个线段树记录询问左端点在不同位置的答案，考察增加操作对线段树的影响，发现只影响 fail 树向上的节点，最后一步动态树优化即可，复杂度 O(nlog2n + mlogn)。

和 BZOJ_2555 相比，这里由于我们不需要强制在线，动态树不需要在后缀自动机插入字符时候跟随 SAM 变化形态，只需要在全部插入完后根据 fail 树构建即可，因而也可以树链剖分啊启发式合并啊替代动态树的环节。

具体来看，先考察 Luogu P6292 区间本质不同子串个数，每次添加新字符时，先把所有位置都加 1，然后类似 dquery 一题的搞法，我们记录上次添加的时刻以去掉重复计数的部分，而这只需要沿着 fail 树向上，并记录每个状态上次计数的时刻即可。这里的线段树只需要支持区间加减，区间求和，因而也可以用树状树组替代。

观察这里的动态树这里其实唯一的用处就只有压缩 fail 树 = =，我们只需要维护上次访问的标记即可，其它信息都可以从 SAM 中拿到，因为 Splay 之后父节点和自己刚好形成压缩后的 endpos 区间。

fzoi 那枚只需要把线段树从区间加常数变成加等差数列。再看 uoj 608，这里我们线段树需要支持的是区间等差数列 checkMax，由于这个标记是单调的，所以可以简单标记持久化，动态树同样只起到压缩 fail 树的功能，完全不用改！

Problem E. I Hate Sigma Problems

询问区间不同元素数目有各种经典离线和函数式线段树做法，但是这个题要统计整体，直接上数据结构复杂度反而不太对。
我们可以单独统计每种元素对答案的贡献，而这个只要计算其补集即可，复杂度 O(n)。
https://atcoder.jp/contests/abc371/submissions/57884316

Problem G. Lexicographically Smallest Permutation

原题等价于求字典序最小的 AP^x，由于 P 是个排列，显然可以只考察它的循环分解。我们从左到右贪心的确定 AP^x 的每一位以及打包得到其所在的循环所有位置的结果，按顺序考察每一组这样的循环。我们总能得到一组形如 x = r (mod c) 的限制，这里的 c 是循环的长度，我们要在贪心结果尽可能小的同时，不破坏之前得到的所有限制条件。

我们可以合并这些条件，计算所有这些 c 形成的 lcm，但是这样这个 lcm 可能会特别大。注意到我们并不需要计算具体的 x，并且对于所有互素的 c，显然这些限制是不互相影响的，这提醒我们只需要考察和更新所有 c 的因子所形成的限制条件，进一步我们只需要维护所有素数幂的限制即可。
https://atcoder.jp/contests/abc371/submissions/57872303