前言

众神犇好！这里是一个来自传统弱省JS的高一蒟蒻！

由于NOIP和两轮省选全部起飞没进队QWQ。

没办法只能去THU骗个政策啦！

为什么是“念念不忘 必有回响”呢？其实这是我不知道什么时候从不知道哪里学来的为数不多的句子。大多是之前的爆炸有感而发吧。

一起去的还有高一神犇chy、djydujunyi和高二神犇wyhjohann、gjczgj。他们都太强啦！%%%

顺便说一下高二神犇luhan去参加隔壁的PKUSC啦。

6.4

一大早就到了火车站，五个多小时的火车不多说。然后就转了一个小时的地铁，车内车外两个世界啊啊啊！（帝都真热）

在五道口下的车，然后打车去了西郊（其实走也不要多久）。在某广场上看到了优衣库2333333

西郊真高级！这辈子还没住过多少四星宾馆。填了写信息拿了点东西就和djl（没错就是djl不是djy）住进了预定的房间。（太基啦

（在此处手动为chy点蜡 这是一个住套件的可怜孩子

一进房间我和djl就抢占桌子开始打膈膜。本来我这次就是来锻炼的就不打板子啦。（flag

五点半和大家一起去五道口觅食，路上djl和wyh给我普及了双膝贴创可贴的意思真污。最后选择了康师傅，点了份牛腩饭，米饭少得可怜qwq。中途接到老大消息说要早点回去有话要说，然后窝们就赶紧吃吃吃然后去超市买买买。

话说看到现代牧业打折3瓶只要6块比我们那个小城市不知道高明到哪里去了。

我买了一堆水。感觉第二天要饿死在考场上……

回到宾馆在chy房间集中，老大召唤了will和我们谈经验人生，然后因为省选名次垫底被鼓励了一番。感觉第二天动力满满啊！（flag

回房继续洗澡+洗衣服+膈膜。真是优秀的生活话说我回班上课半个月似乎什么都不记得了，不管了明天随缘。

6.5

早上起来闹肚子，惨啊（RP++

然后因为这个和djl去餐厅晚了连座位都没有，还好后来抱了gj和wyh大腿……早饭也就是一般的自助餐，期间闹了个很囧的事。

我和djl来到饮料桶前。

djl：“麦片看起来不错，我来加点冷牛奶……woc怎么是黄的。”

我看了看，旁边是写的冷牛奶不错。然后我也加了点，woc怎么是热的。

然后窝们又加了点热牛奶，回去了。

djl：“你有没有觉得这个牛奶是豆浆味的……”

还真是……

结果一看，是热豆浆……标签的位置有些鬼畜，不知道被谁动过了qwq（RP++

上车去thu啦。满眼熟悉的景象。去年创新班的时候来过，还在草坪前合了影，这次又合了影。感觉一年过后自己变了不少。

绕着thu转了小半圈，感觉看见了三四个操场，实际上个数还要多。（毕竟体育学校嘿嘿嘿）

转了回来我们先自己合了影，然后就被领过去大合影。傻不拉几的站在架子上好久，感觉是先给家长老师们摆拍。当然也有可能是摄影师的照相机爆炸了旁边是djl，再旁边是一中的三个神犇krydom和他的好基友们，斜后方是萌萌哒的城里人dzj。

其实我这个时候还是不认识吴文虎老教授的。

然后就去礼堂听讲座。影响最深的就是吴教授是合唱团团长（后来看了学长的游记发现这件事吴教授每年都要炫耀一次）……其他也没什么了。

老大中途发来消息说早点试完机，他要请吃饭。

然后就去东主楼试机。空调开得很冷，幸亏我带了衣服。不过当时似乎已经快十一点了，饿啊……我已经没力气敲键盘了！然后随便把提答搞了搞输了一堆1骗了100……

wyh自告奋勇当导游，然后又闹了个很囧的事。

wyh带着我们一直走啊走……他现在一人五命啊！

走了半天，wyh：“woc导航怎么不灵了！”

走了半天，我们似乎走到了一个奇怪的地方，感觉离学校中心越来越远了。

走了半天出现了一个水站，wyh买了瓶葡萄味的矿泉水（误）然后带我们继续走。

我们虔诚地跟着导航，结果被告知在出校门10米处停下来……

迷路了？

wyh问门卫：“***该往哪走啊……你看手机上写的这里啊。”

门卫：“这以前是老***啊，要往前走再左拐。”

那么我们要回到很久之前我们来过的地方？

惨啊……

辣鸡导航。wyh该换手机了……（全体RP++

原来老大已经和xy、xzh、gyh、xyue等了好久了，那就吃吃吃吧。

可以看出来大家都很拘谨，老大喝了好多酒，chy问了xzh很多问题，我wyh和gj吃了很多菜，djl一个人默默地吃了很多很多肉。

老大讲述了xy以前爆炸的事例和xyue骗分的光辉事迹，我心想这次本来就是来玩玩的，就放开来乱搞吧。

吃了好久……话不多说。不过没有饭真是差评。还好我带了面包，半只北海道。

然后xzh带我们去某教学楼休息，我们大概算好了时间，休息完了就出发了。

东主楼……

一片奇怪的气氛……

据说比赛延时了？两点半？

我们找了个会议室休息，结果我和大部队分开了，坐在某个角落里玩手机。

过了一会……“比赛延迟到三点。”

UOJ群里炸开了锅。

萌萌哒vfk说是虚拟机问题。

可是马上就三点了呀。

果不其然……“比赛延迟到三点半，非常抱歉。”

会议室里也开始沸腾了，其实这个时候大家的心态都发生了微妙的变化，这个时候就比谁更能沉得住气。

我仍旧是玩手机，玩会休息会。

感觉午饭都消化光了……不过听说比赛中途有汉堡，这还不错。

然后就比赛啦。

先通览了一发题面，感觉T2是道思博题？然后就愉快地码码码，心想这次肯定有很多人A题吧。

然后过了半小时，发现可持久化trie出了一些bug，修复了一会儿。

过样例了！交一发，结果只对了两个。

然后我思考了一会儿题意，感觉虽然样例过了，但是思路不怎么对。然后就又调了近一个小时中途发现对拍的暴力写错了，开始方张起来。

过了一会儿，我发现自己就是个智障……！之前的题意都理解错了，脑子里混乱不堪。然后定下心来再想了想，感觉再记个历史最大值就可以了。

两个半小时过去了……我真是弱啊不过还好发现了错误不然就一题都A不了了qwq

然后我开始吃汉堡+想T1。先水掉了前面单调的20。感觉单峰的也是$\mathcal{O}(n^2)$的，然后想了一会儿gg了。感觉$n=50$可以做到$\mathcal{O}(n^4)$，然后就发现了子问题，可以决策啦。

不过中途我又闹肚子了……初步怀疑是汉堡导致的。不过我借上厕所的时间又好好证明了一下单峰的DP，又想了会儿一般情况，感觉只会状压……

花了一个小时码完了70，然后对拍+看提答。过了一会感觉没什么问题就交上去了。

已经三个半小时过去了。我在纠结认真想T1的多项式算法还是看看提答的特殊点。想了一会儿T1，感觉只要在单峰的基础上限定上下界？但是过了一会发现是错的而且不知道怎么修正，就没写下去。

然后花了十来分钟把提答两个环的点水过了。发现后面的点要么是离得很远，要么是互相交叉……感觉完全不会啊……

算了写个爆搜骗骗分吧……然后我的一个小时就献给了爆搜的调试……qwq

调了半天终于对了，我设置了一下搜索的状态数，开了臭氧优化跑后面的大点。$n$比较小的时候我设置每个点最多搜5个状态，大一些就两三个。

然后跑了十几分钟一直跑到了七号点。检查了下……woc怎么和checker给的长度不一样？checker似乎比我程序算得更短？哪有这种事的……不管了能有分就行。

由于我搜索的状态是一起提出来然后按照某些值排序，每个点都要占用$\mathcal{O}(m)$的空间，结果最后三个点华丽丽地爆栈了……我却不知道……我还把状态数设置成了1，发现还是RE。然后就蒙了……我考场上怎么就没想到直接取min呢？？？？？？？？？？？？？

最后只能直接按照输入顺序输出拿1分了……qwq（人傻不能怪党

出了考场，发现除了gj都炸了？djl还交错了文件……wyh和chyT2没想到历史最大值悲剧50分。

我似乎校内rank2了？

回来在车上和外校的同学讨论了一下T1，发现他们有一些神奇的做法，当然也有跟我那个错误想法一样的，不过他们没想出反例……为他们祝福……

大概算了算有70+100+28+一堆运气。gj也是这样的，但显然他的搜索方法比我高明得多。感觉没上200非常地伤心。

然后和djl看了会鬼畜视频就睡觉了。

6.6

早上起来抢位置啦。结果djl在馄饨汤里面发现了一只苍蝇………………………………………………………………

【呕

然后窝们就回到房间等电话。

激动地点开UOJ群，发现各位都在交流有没有接到电话。

“我接到啦！”*n，“我还没接到qwq”*n……

其实这个时候我还是很虚的。

还没接到就说明我的成绩可能已经不是靠前的了。qwq

9:33……

这个时候我正好在厕所里……

然后！电话响了！

激动！兴奋！

然后就是一些大家都知道的内容。问了问学校的其他人，gj也接到了，这可能意味着其他人都咸鱼。

到了某会议室，发现今年是按照拼音倒序的，资慈啊！于是我就是前几个的啦。

问了一些奇怪的生活问题，我脑子一热说了一大通，结果似乎TLE了……？

回到chy房间，他们似乎是要离开了呢……我要和gj睡一晚qwq

中午老大请吃饭。然后下午去参加了那个毫无时间观念的闭营式，gj拿了三等，窝是二等……但是gj是正式选手啊！祝他NOI拿Au！

然后老大带我们去参观了今日头条，上下两层千人办公室……非常地显眼。

（由于要期末考 缓更

期末考炸了不开心

UOJ#38 玛里苟斯 题解

题面在这里

简要题意

原题已经非常非常地简要辣！细化一下数据范围：

题♂解♂

鉴于网上的题解都很神，然而这题比题解更神，我这个退役选手只能自己写一份题♂解♂造福大众辣。

首先答案的大体形式是$\displaystyle E=\frac{\sum_{i=1}^{2^n}x_i^k}{2^n}$，其中$x_i$是一些数异或出来的结果。

我们注意到一个性质，如果$S$的一个子集$A$和$a_i \not \in A$，其中满足$A$中所有元素的异或为$a_i$，那么我们可以把$a_i$删掉，而答案不改变。这是因为去掉$a_i$后，方案数除以了$2$，同时分子上的数也除以了$2$，原先每个数都与$A$中的异或和异或了一遍，又跟$a_i$异或了一遍。

但是线性基有$\mathcal{O}(\log_2a_i)$个，总的方案数也就是$\mathcal{O}(2^{\log_2a_i})=\mathcal{O}(a_i)$的，只能做$k \geqslant 3$的情况。

$k=1$

由于是线性的期望，对于这种问题我萌当然按位考虑啦。假设当前统计第$i$位的贡献，那么当且仅当这位上异或出来是$1$才有意义，也就是说在第$i$位上，选择了奇数个$1$。

设第$i$位上有$a$个数是$1$，$n-a$个数是$0$。那么这一位的贡献就是：

$\displaystyle 2^i \times 2^{n-a} \sum_{q=1}^{\lfloor \frac{a+1}{2} \rfloor} \mathrm{C}_a^{2q-1}$

其中$2^{n-a}$是因为$0$可以随便选。

什么？你没有看错！组合数奇数位置上的和不就是$2^{a-1}$嘛！于是就变成了

$\displaystyle 2^i \times 2^{n-a} \times 2^{a-1} = 2^i \times 2^{n-1}$

当然这里必须要$a>0$，否则这一位的贡献就是$0$。

于是

$\displaystyle E=\frac{\sum_{i=0}^{63}\left(2^i \times 2^{n-1} \quad | i位有1 \right)}{2^n} = \sum_{i=0}^{63}\left(2^{i-1} \quad | i位有1 \right)$

所以把所有的$a_i$用$\mathrm{or}$连接，就可以知道哪些位有$1$，答案也就是$\mathrm{or}$出来的值$\div 2$。同时，我们会发现这里如果有小数部分，只可能是$0.5$，$i=0$时特判一下即可。

时间复杂度$\mathcal{O}(n)$。

$k=2$

这个时候我萌要多讨论一下。为了延续之前的经验，我们要尝试按位统计。

把一个二进制数的每一位列出来，那么可以得到：

$\displaystyle E=\frac{\sum_{i=1}^{2^n} \left( \sum_{j=0}^{31}b_{i,j} \times 2^j \right)^2}{2^n}=\frac{\sum_{i=1}^{2^n} \left(\sum_{j=0}^{31} b_{i,j} \times 2^j\right) \left( \sum_{p=0}^{31} b_{i,p} \times 2^p \right)}{2^n} = \frac{\sum_{i=1}^{2^n} \sum_{j=0}^{31} \sum_{p=0}^{31} b_{i,j} \cdot b_{i,p} \cdot 2^{j+p}}{2^n}$

让我萌来交换求和顺序：

$\displaystyle E=\sum_{j=0}^{31} \sum_{p=0}^{31} 2^{j+p}\frac{\sum_{i=1}^{2^n}b_{i,j}b_{i,p}}{2^n}$

接下来就是统计某一个异或出来的数的第$j$位和第$p$位同时是$1$的方案数啦。也就是说，要选取一些数，使得它们第$j$位和第$p$位上$1$的个数都是奇数。

$j=p$的情况

这和$k=1$是几乎一样的，就变成了

$\displaystyle 原式=\sum_{j=0}^{31}2^{2j} \frac{\sum_{i=1}^{2^n}[b_{i,j}=1]}{2^n}=\sum_{j=0}^{31}2^{2j} \frac{\sum_{i=1}^{2^n}b_{i,j}}{2^n}=\sum_{j=0}^{31} 2^{2j}\left( \sum_{q=1}^{\lfloor \frac{a+1}{2} \rfloor} \mathrm{C}_a^{2q-1} \right) 2^{n-a} \frac{1}{2^n}=\sum_{j=0}^{31}\left(2^{2j-1} \quad |第j位上有1\right)$

$j \not =p$的情况

$\displaystyle 原式=\sum_{j=0}^{31} \sum_{p \not =j} 2^{j+p} \frac{\sum_{i=1}^{2^n}[b_{i,j}=1 且 b_{i,p}=1]}{2^n}=2\sum_{j=0}^{31} \sum_{p>j}2^{j+p} \frac{\sum_{i=1}^{2^n}[b_{i,j}=1 且 b_{i,p}=1]}{2^n}=\sum_{j=0}^{31} \sum_{p>j}2^{j+p} \frac{\sum_{i=1}^{2^n}[b_{i,j}=1 且 b_{i,p}=1]}{2^{n-1}}$

两个位置$(b_{i,j},b_{i,p})$一共有四种情况：$(1,1)$，$(1,0)$，$(0,1)$，$(0,0)$。设这两位上有$a$个$(1,1)$，$b$个$(1,0)$，$c$个$(0,1)$，$n-a-b-c$个$(0,0)$，那么我萌要从中选取一些，使得均有奇数个$1$。因此不妨设取$x$个$(1,1)$，$y$个$(1,0)$，$z$个$(0,1)$，$(0,0)$随便取，那么要有$x+y=奇数，x+z=奇数$。分$x$的奇偶讨论，可以很快地得到：

$\displaystyle \mathrm{C}_a^奇\mathrm{C}_b^偶\mathrm{C}_c^偶2^{n-a-b-c}=2^{n-3}$

$\displaystyle \mathrm{C}_a^偶\mathrm{C}_b^奇\mathrm{C}_c^奇2^{n-a-b-c}=2^{n-3}$

注意，这是在$a,b,c>0$时成立的，如果其中有$0$，那么有的数就被强制选了偶，中间组合数求和的结果也会不一样。细节参考程序。

所以直接这样求和即可。

时间复杂度$\mathcal{O}(n \log_2^2n)$。

$k \geqslant 3$

这个时候可以高斯消元啦。消完了直接暴力枚举异或方案。但是要注意到，中间过程求和是可能爆long long的，要自己手写小高精。

代码（C++）

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int L = 2000005, N = 100005;
char buf[L], *p = buf;
template <typename T> void rd(T &t) {
    t = 0;
    while (*p < 48 || *p > 57) ++p;
    do {(t *= 10) += *p - 48; ++p;} while (*p > 47 && *p < 58);
}
int n, k;
ull a[N];
void s1() {
    ull ans = 0;
    for (int i = 1; i <= n; ++i) ans |= a[i];
    cout << ans / 2; if (ans & 1) cout << ".5"; cout << endl;
}
void s2() {
    int m = 0, i, j, k, x, y, z, p, q;
    ull ans = 0;
    bool frac = false;
    for (i = 1; i <= n; ++i) m |= a[i];
    for (j = 1; j < 32; ++j)
        if (m & (1ULL << j)) ans += 1ULL << (2 * j - 1);
    if (m & 1) frac = true;
    for (j = 0; j < 31; ++j)
        for (k = j + 1; k < 32; ++k) {
            x = y = z = 0;
            for (i = 1; i <= n; ++i) {
                p = a[i] & (1ULL << j); q = a[i] & (1ULL << k);
                if (p) if (q) ++x; else ++y;
                else if (q) ++z;
            }
            if ((x && y && z) || (x && y && !z) || (x && !y && z) || (!x && y && z)) ans += 1ULL << j + k - 1;
            if (x && !y && !z) ans += 1ULL << j + k;
        }
    cout << ans; if (frac) cout << ".5"; cout << endl;
}
void s345() {
    int i, l, j, S, tmp;
    ull s, p, q, z1 = 0, z2 = 0, b;
    for (i = 0, l = 1; i < 21; ++i) {
        for (j = l; j <= n; ++j) if (a[j] & (1 << i)) break;
        if (j > n) continue;
        swap(a[l], a[j]);
        for (j = 1; j <= n; ++j)
            if (j != l && (a[j] & (1 << i))) a[j] ^= a[l];
        ++l;
    }
    --l;
    for (S = 1; S < (1 << l); ++S) {
        tmp = p = 0; q = 1;
        for (i = 1; i <= l; ++i)
            if (S & (1 << i - 1)) tmp ^= a[i];
        for (i = 0; i < k; ++i) {p *= tmp; q *= tmp; p += q >> l; q &= ((1 << l) - 1);}
        z1 += p; z2 += q;
    }
    z1 += z2 >> l; z2 &= (1 << l) - 1;
    cout << z1; if (z2) cout << ".5"; cout << endl;
}
int main() {
    fread(buf, 1, L, stdin);
    int i;
    rd(n); rd(k);
    for (i = 1; i <= n; ++i) rd(a[i]);
    if (k == 1) s1();
    else if (k == 2) s2();
    else s345();
    return 0;
}

完结撒花！

毕姥爷太强啦！

UOJ#38 奇数国 题解

题面在这里

简要题意

有$100000$个数，每个数的质因子只会是前$60$个素数（$2 \sim 281$）。一开始每个数都是$3$，有$x$个操作，每次要么修改一个数，要么询问一段区间内的数的乘积的欧拉函数模$19961993$的值。$x \leqslant 100000$，过程中每个数不会超过$1000000$，每次询问的乘积不会超过$10^{18}$。

题♂解♂

虽然这个题目非常地神，鉴于网上的题解都很神，我这个退役选手只能自己写一份题♂解♂造福大众辣。

根据欧拉函数的性质，设$\displaystyle a=\prod_{i=1}^{60}p_i^{k_i}$，那么$\displaystyle \varphi(a)=\prod_{i=1}^{60}\left(p_i^{k_i-1}(p_i-1)\quad | k_i>0\right)=\left[\prod_{i=1}^{60}\left(p_i^{k_i-1}\quad |k_i>0 \right)\right]\cdot \left[\prod_{i=1}^{60}\left(p_i-1\quad |k_i>0\right)\right]$。

这个东西用线段树直接维护非常烦，我们把相同格式的分开来维护。

设$\displaystyle \alpha(a)=\prod_{i=1}^{60}\left(p_i^{k_i-1}\quad |k_i>0 \right)$，那么：

$\displaystyle \varphi(a)=\alpha(a)\prod_{i=1}^{60}\left(p_i-1 \quad | \quad p_i | a\right)$

$\displaystyle \alpha(ab)=\alpha(a)\alpha(b)\prod_{i=1}^{60}\left(p_i \quad | \quad p_i|a 且 p_i|b\right)$

$\displaystyle \varphi(ab)=\alpha(ab)\prod_{i=1}^{60}\left(p_i-1 \quad | \quad p_i|a 或 p_i|b\right)$

于是线段树上只要维护$\alpha(当前域的乘积)$和当前域的乘积是否含每个质因子。为了快速求后面的那两个乘积，我们还可以每$20$个质因子状态压一个位，预处理$p_i$和$p_i-1$的乘积，线段树上用$\mathrm{and}$和$\mathrm{or}$合并状态即可。

时间复杂度$\mathcal{O}(x \log_2100000)$。

代码（C++）

#include <bits/stdc++.h>
using namespace std;
const int N = 100005, M = 282, pm = 19961993, L = 2000005, TM1 = (1 << 19) + 1, TM2 = (1 << 20) + 1;
char buf[L], *p = buf;
void rd(int &t) {
    t = 0;
    while (*p < 48 || *p > 57) ++p;
    do {(t *= 10) += *p - 48; ++p;} while (*p > 47 && *p < 58);
}
bool vis[M];
int cnt[60], q[M], fun[TM1], pro1[TM2], pro2[TM2], pro3[TM2], alp1[TM2], alp2[TM2], alp3[TM2];
struct ans {
    int alpha, s1, s2, s3;
} tmp;
ans mge(ans a, ans b) {
    return (ans){1LL * a.alpha * b.alpha % pm * pro1[a.s1 & b.s1] % pm * pro2[a.s2 & b.s2] % pm * pro3[a.s3 & b.s3] % pm,
        a.s1 | b.s1, a.s2 | b.s2, a.s3 | b.s3};
}
struct seg {
    int alpha, s1, s2, s3;
    seg *lc, *rc;
    void init() {s1 = 2; s2 = s3 = 0; alpha = 1;}
    void upd() {
        s1 = lc -> s1 | rc -> s1; s2 = lc -> s2 | rc -> s2; s3 = lc -> s3 | rc -> s3;
        int t1 = lc -> s1 & rc -> s1, t2 = lc -> s2 & rc -> s2, t3 = lc -> s3 & rc -> s3;
        alpha = 1LL * lc -> alpha * rc -> alpha % pm * pro1[t1] % pm * pro2[t2] % pm * pro3[t3] % pm;
    }
    void mdf(int l, int r, int x, int y, int ts1, int ts2, int ts3) {
        if (l == r) {alpha = y; s1 = ts1; s2 = ts2; s3 = ts3; return;}
        int mid = l + r >> 1;
        if (x <= mid) lc -> mdf(l, mid, x, y, ts1, ts2, ts3); else rc -> mdf(mid + 1, r, x, y, ts1, ts2, ts3);
        upd();
    }
    ans qry(int l, int r, int ll, int rr) {
        if (ll <= l && r <= rr) return (ans){alpha, s1, s2, s3};
        int mid = l + r >> 1;
        if (rr <= mid) return lc -> qry(l, mid, ll, rr);
        if (ll > mid) return rc -> qry(mid + 1, r, ll, rr);
        return mge(lc -> qry(l, mid, ll, rr), rc -> qry(mid + 1, r, ll, rr));
    }
} *rt, pool[N * 2], *tail = pool;
void build(seg *&rt, int l, int r) {
    rt = tail++;
    if (l == r) {rt -> init(); return;}
    int mid = l + r >> 1;
    build(rt -> lc, l, mid); build(rt -> rc, mid + 1, r);
    rt -> upd();
}
int main() {
    int r = 0, i, j, S, t, op, x, y, tq, s1, s2, s3;
    for (i = 2; i < M; ++i) {
        if (!vis[i]) q[r++] = i;
        for (j = 0; j < r && i * q[j] < M; ++j) {
            vis[i * q[j]] = true;
            if (!(i % q[j])) break;
        }
    }
    for (i = 0; i < 20; ++i) fun[1 << i] = i;
    pro1[0] = pro2[0] = pro3[0] = alp1[0] = alp2[0] = alp3[0] = 1;
    for (S = 1; S < (1 << 20); ++S) {
        t = S & -S; i = fun[t];
        pro1[S] = 1LL * pro1[S - t] * q[i] % pm;
        pro2[S] = 1LL * pro2[S - t] * q[20 + i] % pm;
        pro3[S] = 1LL * pro3[S - t] * q[40 + i] % pm;
        alp1[S] = 1LL * alp1[S - t] * (q[i] - 1) % pm;
        alp2[S] = 1LL * alp2[S - t] * (q[20 + i] - 1) % pm;
        alp3[S] = 1LL * alp3[S - t] * (q[40 + i] - 1) % pm;
    }
    fread(buf, 1, L, stdin);
    build(rt, 1, N - 5);
    rd(tq);
    while (tq--) {
        rd(op); rd(x); rd(y);
        if (op) {
            memset(cnt, 0, sizeof(cnt));
            s1 = s2 = s3 = 0;
            for (i = 0; i < r; ++i)
                if (!(y % q[i])) {
                    if (i < 20) s1 |= 1 << i; else if (i < 40) s2 |= 1 << (i - 20); else s3 |= 1 << (i - 40);
                    while (!(y % q[i])) {y /= q[i]; ++cnt[i];}
                }
            for (i = 0; i < r; ++i)
                for (j = 1; j < cnt[i]; ++j) y *= q[i];
            rt -> mdf(1, N - 5, x, y, s1, s2, s3);
        } else {
            tmp = rt -> qry(1, N - 5, x, y); s1 = tmp.s1; s2 = tmp.s2; s3 = tmp.s3;
            printf("%d\n", 1LL * tmp.alpha * alp1[s1] % pm * alp2[s2] % pm * alp3[s3] % pm);
        }
    }
    return 0;
}

完结撒花！

UOJ#37 主旋律 题解

题面在这里

简要题意

简明扼要的题♂意♂，求一个$n$个点、$m$条单向边的图中，有多少边集去掉后使得原图不强联通。$n \leqslant 15,0 \leqslant m \leqslant n(n−1)$。

题♂解♂

鉴于网上的题解都很神，跳过了好多好多好多关键部分，我这个退役选手只能自己写一份题♂解♂造福大众辣。

借鉴自陈老师的slides。

首先，原问题完全等价于求有多少边集保存下来使得原图强联通。然而这是一个非常非常复杂的问题，我们来考虑反面，有多少边集保存下来使得原图不强联通（给它一个奇妙的缩写叫不强连通数），最后用$2^m$减去这个值就是答案。

方法一

由于不强联通，把图中的强连通分量缩点后，一定形成了一幅DAG。接下来我们来考虑一个Naive的做法，枚举所有可能的SCC缩点情况，DP计算DAG的个数。

设$f[S]$表示点集（缩过SCC后的一个映射，也就是说这个点集里不存在SCC）是$S$的情况下的DAG个数。因为一个DAG一定包含一些入度为$0$的点；同时已经有一个DAG时，如果再往里面加一些入度为$0$的点，并将这些新加的点向已有的点随意连边（单向的），所得的图还是DAG。我们来枚举这些入度为$0$的点，但是存在一些情况并不能恰好精准地枚举完（不能保证剩余的点中没有入度为$0$的点），因此采取容斥。

在枚举SCC后，可以得到这个式子：

$\displaystyle f[S]=\sum_{T \subset S, T \not = \varnothing} (-1)^{|T|-1} \times 2^{cross[T][S-T]} \times f[S-T]$

其中，$cross[T][S-T]$表示$T$集合中的点向$S-T$集合中的点连的边数（单向的），由于可以随意连边而不破坏DAG，因此是$2^{cross[T][S-T]}$。但是……太慢啦！枚举SCC的复杂度窝不会算，反正很大就是了。这个DP的复杂度是$\mathcal{O}(m3^n)$（包括了算$cross[T][S-T]$），实在是太慢了。

方法二

稍加分析便会发现，上面这个做法是没必要枚举SCC的。在$T$中放了奇数个SCC的时候，上面的符号是$+$，偶数个是$-$，再乘上SCC的划分方案数就可以了。

我们设$T$的一个划分方案是$A_T={A_1,A_2,\ldots,A_k},A_i$是点的集合，满足$\displaystyle \forall_{1 \leqslant i < j \leqslant k}, A_i \bigcap A_j=\varnothing, \bigcup_{i=1}^k A_i=T$。也就是说，我们只需要知道$k$而不需要具体地知道每个$A_i$，同时也避免了枚举SCC。上面的式子可以写成：

$\displaystyle f[S]=\sum_{T \subset S, T \not = \varnothing} \sum_{1 \leqslant k \leqslant |T|} (-1)^{k-1} \times g_k[T] \times 2^{cross[T][S-T]} \times 2^{h[S-T]}$

其中$g_k[T]$表示把$T$划分成$k$个SCC的方案数，$h[S]$表示起点和终点都在$S$集合中的边的条数。

进一步，把所有的奇数$k$一起考虑，偶数也一起考虑，那么就可以写成：

$\displaystyle f[S]=\sum_{T \subset S, T \not = \varnothing} \left(\sum_{k=1}^{\lfloor \frac{|T|+1}{2} \rfloor}g_{2k-1}[T]-\sum_{k=1}^{\lfloor \frac{|T|}{2} \rfloor} g_{2k}[T]\right)2^{cross[T][S-T]} \times 2^{h[S-T]}$

所以我们只要预处理出$\displaystyle \sum_{k=1}^{\lfloor \frac{|T|+1}{2} \rfloor}g_{2k-1}[T]-\sum_{k=1}^{\lfloor \frac{|T|}{2} \rfloor} g_{2k}[T]$和$cross[T][S-T]$就可以辣！

定义$\displaystyle p[S] = \sum_{k=1}^{\lfloor \frac{|S|+1}{2} \rfloor}g_{2k-1}[S]-\sum_{k=1}^{\lfloor \frac{|S|}{2} \rfloor} g_{2k}[S]$，$dp[S]$表示集合$S$里的点组成一个SCC的方案数，也就是答案。

$\displaystyle p[S] = -\sum_{T \subset S, u \in T}dp[T] \times p[S - T] + dp[S]$

因为加入了一整个SCC之后奇偶性发生了翻转，要加上负号。始终保证$u \in T$是为了防止重复计数。

$\displaystyle f[S]=\sum_{T \subset S, T \not = \varnothing} p[T] \times 2^{cross[T][S-T]+h[S-T]}$

$dp[S] = 2^{h[S]}-f[S]$

这样就可以顺利DP辣。$cross[T][S-T]$只要边枚举子集边从一个大一点的集合转移过来就可以了。时间复杂度$\mathcal{O}(3^n)$。

代码（C++）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll pm = 1000000007;
const int N = 15;
int out[N], in[N], fun[1 << N], pw[N * N + 5], cnt[1 << N], cross[1 << N];
ll dp[1 << N], all[1 << N], p[1 << N];
int main() {
    int n, m, tn, i, a, b, S, T, rem, t, tmp;
    cin >> n >> m; tn = (1 << n) - 1;
    for (i = 1; i <= m; ++i) {
        cin >> a >> b; --a; --b;
        out[a] |= 1 << b; in[b] |= 1 << a;
    }
    for (i = 0; i < n; ++i) fun[1 << i] = i;
    for (pw[0] = i = 1; i <= n * n; ++i) pw[i] = pw[i - 1] * 2 % pm;
    for (S = 1; S <= tn; ++S) cnt[S] = cnt[S >> 1] + (S & 1);
    dp[0] = all[0] = 1; p[0] = pm - 1;
    for (S = 1; S <= tn; ++S) {
        if (cnt[S] == 1) {dp[S] = p[S] = all[S] = 1; continue;}
        for (i = tmp = 0; i < n; ++i) if (S & (1 << i)) tmp += cnt[S & out[i]];
        all[S] = dp[S] = pw[tmp];
        rem = S - (S & -S);
        for (T = rem; ; T = (T - 1) & rem) {
            t = T | (S & -S);
            if (t < S) (p[S] += pm - dp[t] * p[S - t] % pm) %= pm;
            if (!T) break;
        }
        for (T = S; T; T = (T - 1) & S) {
            if (T == S) cross[T] = 0;
            else {
                t = fun[(S - T) & (T - S)];
                cross[T] = cross[T + (1 << t)] + cnt[in[t] & T] - cnt[out[t] & (S - T - (1 << t))];
            }
            (dp[S] += pm - p[T] * all[S - T] % pm * pw[cross[T]] % pm) %= pm;
        }
        (p[S] += dp[S]) %= pm;
    }
    cout << dp[tn] << endl;
    return 0;
}

完结撒花！

无限ym陈老师。