杭电多校

就只是写一下考场想出来的（大部分码不出/dk），和一些比较妙的不会题。

2023“钉耙编程”中国大学生算法设计超级联赛（1）

1001

要相信我的速度！！！

就是把路径抽离出来然后对每个点做一个EXCRT。

1002

sb树形DP

1003

发现自己爆标了！大概优了一个n！

区间DP，这里想到了一个复杂度相对较优的（大概劣一点也能过）。

我们先设计一个最简单的DP状态，就是f[l][r]表示l到r合成一个的最大收益。我们发现现在还要合几个，就相当于是一个序列，然后其中挖空几段作为f计入贡献，然后剩下的都是一种颜色直接计入答案。我们考虑怎么计算这一部分，我们可以设计状态g[l][r][i]，表示l和r未合过，然后其中包括l和r一共有i个点可以合，剩下的点用f数组合了的答案最大值，发现这个转移是朴素的，每次只考虑枚举中转点然后i转移向i+1，然后就直接O(n^4)，已经爆标了qwq。

但是复杂度可以进一步优化，考虑此题性质是2^i个合并在一起，所以考虑设计状态为g[l][r][i]，表示包括l和r有2^i个值，然后我们发现由两个i转移向i+1的时候接头处被吃掉了一个，所以相当于两个2^i的g转移向了2^{i+1}-1，所以新增数组h[l][r][i]，表示包括l和r有2^i-1个值，然后每次我们由g[i]+g[i]转移向h[i+1]，再h[i]+f转移向g[i]，再g[i]转移向f（表示用掉这些来合成然后卖），所以一共复杂度O(n^3logn)，不知道比标算那个O(n^2m^2R^2)好多少/dx。

1004

计几不会。

1005

用Lyndon或者SA就好了。

1006

就是一个可持久化单调队列的斜率优化。

如果要算出每个点的答案，可以从叶子向上用李超线段树维护凸包同时用线段树合并继承儿子。

1007

我们设计一个k元形式幂级数G(x_1,\cdots,x_k)=\sum_{i_1,\cdot,i_k} c_{i_1,\cdots,i_k}x_1^{i_1}\cdots x_k^{i_k}

c表示这个向量出现次数。

我们要的是F=1+G+G^2+\cdots=\frac{1}{1-G}，也即一个形式幂级数的组合。

对于有障碍的我们就再算一个f_i表示走到第i个障碍的方案，然后容斥一下即可。

接下来考虑k元形式幂级数的卷积。

这里就是EI的维数爆炸解法（cmdblog里面有），我们直接把所有维用变进制数压在一起，为了避免进位问题，我们引入占位函数x(i)=\lfloor\frac{i}{n_1}\rfloor+\lfloor\frac{i}{n_1\times n_2}\rfloor+\cdots，发现x(i)+x(j)=x(i+j)当且仅当没有进位，考虑x(i+j)-x(i)-x(j)\in(0,1)，所以总的<k（除\prod_{i=1}^k n_i下取整必为0），所以可以在模t^k-1意义下循环卷积就有所有情况了。然后可以在第一维DFT后，循环卷积，再IDFT回去，由于k<logn，所以O(knlogn)。

1008

我们可以发现加体力道具收益和休息一样，加速度道具和训练一样。

所以我们发现只要有体力就锻炼，没体力就休息是最优的。

如果n为偶数，那么答案就是(n+2)/2*15。

如果n为奇数，第一次我们考虑race，然后有尽量购买一个50体力药或者两个25体力药，然后就相当于将多的一个回合转换为了50个商店币，然后尽量去买7speed药或两个3speed药，然后分情况算下概率就好了。

1009

sb容斥。

1010

考虑如果比x小了那么永远比x小，所以每个点从比x大到小于等于x只有一个转折点，就是两棵线段树，一棵维护小于等于当前x的，一棵维护大于x的，然后随便搞搞就好了。

1011

发现可以分块，然后在每个块中开一个平衡树。

对于整块，由于变大的只会变大，所以这部分一个加操作即可，剩下部分是区间翻转+加操作。

对于散块，可以暴力重构，但是有更加好的方法。我们考虑抽离出未修改位置，小于x的修改位置，大于等于x的修改位置，然后三个有序序列合并就是线性的了。

平均一下是O(n\sqrt{nlogn})。

1012

考虑SG函数，有SG(u)=(SG(v_1)+1)xor(SG(v_2)+1)xor\cdots(SG(v_l)+1)。

在换根时，考虑有ans(v)=SG(v)xor(ans(u)xor(SG(v)+1)+1)。

所以ANS=\sum[ans(u)>0]/n。

2023“钉耙编程”中国大学生算法设计超级联赛（2）

1001

求出sg函数后发现有一个4k+2的循环节，猜下结论就好了。证明看题解。

1002

每次是从高到低把一段连续0变为1，考虑特殊情况n=1，和贪完剩余操作为奇次时可能将最低位翻为0。

1003

圆方树，题目太长不想看了。

看了一下题解就是有一个trick，考虑能否通过割一个点使得一些关键点两两不连通。一种方法是找出三个点的中心（将它们分开的割点），那么只有可能是这个，试下即可。一种方法是建出圆方树上虚树，如果是菊花且中心是圆点，那么可以。

1004

我们考虑找递推式。我们在剩下n个位时，可以在最后一个放1个，然后剩下显然f_{n-1}是一个下界（相当于有一个位不能用了，也就是当前还堆着其他牌的初始堆不能塞东西进去，所以不能用了），然后剩的n-1个位依次类推，所以就是f_n=\sum_{i=1}^{n-1}(f_i+1)，然后打出表，发现就是f_n=2^{n-1}-1。仔细的证还是移步题解吧。

1005

考虑从右到左扫描线，对于每个左端点，求出一个最小的右端点，使得这个区间的值第k位为1。我们考虑值相当于s_r-s_l+a_l=s_r-(s_l-a_l)。有两种情况，一种是s_l-a_l\geq0，此时我们发现这相当于询问两个数相减的第k位，可以在模2^{k+1}次之后，对于x-y，如果x第k位为1，y第k位为1，且前者前k-1位小于后者，或y第k位为0，且前者前k-1位大于等于后者，如果x第k位为0，类似讨论一下即可。另一种情况s_l-a_l<0，此时相当于一个x+y的第k位，也是类似讨论一下即可。时间O(nlogn)。

1006

计算几何也要适当会嘛。我们对于两两点，考虑所有点是否都在这个有向边的左侧，如果是就连边。最后用floyd跑一边最小环即可。

1007

就是一个bitset优化暴力，有一个细节就是u伸出的两个点中不能有v。

1008

就是一个线段树套矩阵，要仔细审是子序列而不是子串。

如果改问子串，最好写自动机上DP，否则很容易挂（考场写子串就挂了）。

1009

签到题。

1010

可以写线段树优化建图费用流。

题解的做法复杂度更为科学，是考虑dp，dp[i][j]表示最后两个人在i和j的最小花费，我们考虑到把这个转移到dp[j][k]，发现只要满足i+m\geq k 即可，所以就是一个后缀最小值。j表示比i大多少，i在模m意义下滚动，空间就是O(m^2)，时间O(nm)。

1011

我们考虑计算f(n,k)=\sum\limits_{i=k+1}^n\frac{1}{n}\times(p_1-p_{i-1}的最大值在[1,k]的概率)，前面的1/n是最大值位于i的概率。所以f(n,k)=\sum\frac{1}{n}\times \frac{k}{i-1}=\frac{k}{n}\sum_{i=k}^{n-1}\frac{1}{i}，可以直接暴力，可以三分，可以求导出k=n/e最大，然后枚举上下30个（这题1个就行了）。

1012

我们就朴素的建网络流图，每个点都一分为二来限制上界。然后每次涉及到的两个点我们建出新的，剩下重复利用，对于每次的两个我们连边x\rightarrow y^{'}，y\rightarrow x^{'}，流量为1即可。最后一遍最大流。

1013

计几+多项式，不会。

2023“钉耙编程”中国大学生算法设计超级联赛（3）

1001

1002

六维偏序（K表示维数），被吓到了。

我直接一个百度，得到在六维偏序计算逆序对的时候，可以对每一维开n个bitset，然后对于每个数，我们把比他小的数的bitset（预处理每维前缀对应的bitset）拿来&一下然后count就好了。但是空间会爆，所以我们分块（长度B），然后每次一个块和剩下数计算，还有一个块内计算，这样的话每次bitset等数组只用开根号个长度根号的，且复杂度未变。

说了这么多，这题并没有解决。

我们手写bitset！我们对于每个二进制压位数（压C位）（对应包含的i集合不同），处理出来我可以拿的为sta时的最大值，这里的时间复杂度是O(\frac{n}{B}\frac{B}{C}2^C)=O(\frac{n2^C}{C})，我们剩下就和上面是一样的，就是O(K\frac{n}{B}n\frac{B}{C})=O(\frac{Kn^2}{C})。我们手玩/尝试得出C=17是比较优的，可以通过此题。

感觉挺有教育意义的。

1003

1004

其实就是暴力，我们对于1和每个i配对，然后得到一组，我们拿来验证一下，具体就是看看(xj+dx,yj+dy)和(xj-dx,yj-dy)是否有其中一者，有就可能可以配对，又全部随机所以产生矛盾的概率很小。如果dx!=0||dy!=0，那么-dx和-dy也是一组解，否则记一次。考虑几个极端情况，当只有两个的时候，也就是一个斜线，那么我们可能会搞出一个121的东西（也就是有一个位置重了），那么处理不好会出现重复的解，所以要去重。还有一个就是1点坐标和i点重了，那么我们会拿(0,0)来试，但是如果像我一样用set来维护哪里有值，就可能出现自己和自己配对，那么就一定会判为合法，就假了，所以要用map，如果dx=dy=0，要在去掉自己后再判。

1005

先离散，考虑DP，用f_{i,j}表示一共i个数，最大值是j的方案数，转移j不变的时候判一下有没有多的数可以用，j变的时候用一个前缀和优化即可。

1006

1007

1008

1009

1010

由于随机，所以有一个结论就是如果用段来维护可达位置，那么只有O(1)个段。所以就可以直接线段树维护这个，暴力两两做，然后把重叠的合并，复杂度就是O(nlogn)了。

考虑感性理解这个结论。非常感性的证明是我们由于是随机，所以不妨假设都在三等分点，然后算一下就只有一段就好了（虽然看起来很假，但常常可以帮我们找结论，考场感性证明）。一个相对理性的证明是首先对于n个取i个形成的段不难理解成O(1)（这个比较显然？），然后考虑不同i之间的，如果i与i+1之间不重叠，那么有最大的i个r之和小于最小的i+1个l之和，由于随机分布，所以r-l可以理解成O(n)的（这个可以算期望），而l也是O(n)级别，所以就是i个O(n)之和小于O(n)，显然这个概率在i不断变大的时候概率越来越小，所以概率之和感觉上就是一个快速收敛的东西，同时显然O(lnn)就是一个级松的上界了（可以把i个O(n)之和从类似二项式分布（不会概率/kk）看成一个均匀分布的来算就是O(nlnn)），作为复杂度也可以过题了。

1011

我们考虑每个新格子是由哪些和过来的，然后暴力判一下这些是否都一样就好了，n很小，怎么暴力都行。

1012

这道题比较有意思，我的map套map再次出山了，这次更加厉害，有一维是pair的，另一维我还暴力做了前缀和/dx。

我们考虑怎么做，首先一对数a,b，有a>b，那么一定是由a-b,b转移过来的，然后用辗转相除法的过程，那么就是一维固定为b，另一维为a-kb这样子的等差数列，形如这样的等差数列有nlogn个。我们以一维的值，和另一维等差数列的首项为代表元存储这个等差序列（考虑等差序列公差就是另一维的值）（考虑首项一定是a%b，因为不然的话a还是比b大可以继续减）。对于每个代表元开一个map维护a-kb中的k，所以就有了一个map套map。考虑一下如果可以由A,B转移过来的话，以A>=B为例，那么一定是B和A%B为代表元且k>=A/B，可以总的前去比A/B小的最大一个对应的前缀和，这里发现A,B不可能在两个等差数列所以两对数不会对它重复贡献，我们A>=B算一次再abABswap后A>=B算一次刚好包含所有情况。这里漏了一个情况就是a==b的时候，我们发现只可能是A0或0A转移过来，又A和B不为0，所以只可能a=b=A=B，特殊处理一下就好。

2023“钉耙编程”中国大学生算法设计超级联赛（4）

1001

1002

考虑子树内怎么做，可以线段树合并+线段树二分。（注意，牢记线段树二分这个trick，不要突然失忆）考虑子树外怎么做，我们在线段树里面维护有删除的点的答案，然后分开两部分计算，一个是有删除的部分的max，一个是没删除的部分的max。前面这个就是这种特殊线段树的特殊合并（相当于维护了tot-x，所以合并后还要减tot，也即tot-x+tot-y-tot=tot-x-y），以及线段树二分。后面这个可以树形dp，朴素但是细节多。一种更好的方法是构建一个可持久化的整树，然后在残树线段树合并的时候一起合并。具体就是如果残树return了，那么整树也可以直接继承对应的点的信息然后return，儿子处特殊处理，由于操作次数和残树一样，所以复杂度对。

1003

简单双指针扫一下即可。

1004

考虑每个点的概率是独立的，可以分别计算再相加就是期望。所以答案就是n*单点概率。考虑计算后者，我们用一个二重的东西来转移，一个表示k次后，在原位的概率，一个表示不再原位的概率，然后就可以矩快快速转移了。

1005

不难，但是细节多。

1006

简单题。

1007

使用mobius反演，有ln\ n=\sum_{d|n} S(d)，所以n=\prod_{d|n} ans(d)，那么我们先考虑d是1，所以ans(1)=1，然后有ans(p)=p，然后有ans(p^k)=p，然后有ans(p1p2……)=0。就可以mr快速计算了。

1008

考虑莫反之后的式子，我们枚举的d一定是i的因子。接下来考虑fail树上dp，维护一个桶，第i位表示这个点到根路径上满足j=ki的权值和。考虑复杂度，加入一个点，要在对应因子位加，那么是n/1+n/2+\cdots=O(nlnn)，查询类似分析。

1009

该式子就是\sum/\tbinom{n}{k}。先考虑k=2的情况，依次考虑每条边(u,v)，那么我们先对于每个点求出来f_x表示x子树内，去掉颜色为c(fa_x,x)的对应子树之后有多少个点，这个可以让每个点对第一个出现相同颜色的祖先做一次贡献来计算。要跨过(u,v)，所以一个端点的可取点数就是f_u，另一个端点，考虑如果有一个祖先颜色和这个边一样，那么就是f_p，否则是根节点去掉颜色c的子树，这个也是可以预处理的。k>2的时候其他点任选，多乘\tbinom{n-2}{k-2}即可。

1010

简单结论题。

1011

简单题，注意thick twice,code once，尽量用方便的写法。

1012

简单排序题。

2023“钉耙编程”中国大学生算法设计超级联赛（5）

1001

考虑每个点和每个线段计算一个值。这里教会了我一件事，就是为了保证精度，绝对不要有一个intmax的东西平方又开根，这样子小数位绝对挂。为了精度尽量正确，由于要保证小数位，而开根是整数位和小数位分开开根的，又是优先保证整数位精度，那么很有可能会出现整数位有16位，那么小数位准的只有2位了，那么开根的时候，如果要保留4位，我们需要精确的就是8位，那么很可能爆精。所以最好解决方法是尽量把开根变成除法。这里就是我把垂点在线段上时的情况，改点积+勾股，变成了叉积就好了。

1002

推一下发现gcd(2^a-1,2^b-1)=2^{gcd(a,b)}-1，就随便推一下莫反，最后式子把k用二项式展开，就是要求id_p*\mu的块筛，那么我们就发现id_p*\mu*I=\sum id_p，所以可以杜教筛。

1003

我是直接写1004的。

1004

考虑回文串只有O(n)种，先暴力PAM一次求出有哪几种回文串，然后hash暴力判哪些是双回文串，然后再跑一遍PAM，算出PAM树每个节点到根一段路上有几个双回文串。于是就解决了。

1005

可以使用生成函数，但是不熟。

我们考虑最后计算方案数的时候，我们给每组一个标号，然后用插板来划分组，然后发现标号去掉是\frac{1}{m!}，然后点随机撒进去是n!的，所以变成插板，每个板距离是[1,k]的，可以容斥几个位置不满足解决。

1006

简单DP。

1007

考虑要计算的是(px+1-p)^n的第k项乘上s_k，这是简单的。i^m的处理可以欧拉筛O(n)。

1008

我们考虑对于\sum\limits_{i=0}^n i^m=\sum\limits_{i=0}^m a_in^{\underline{i}}。

考虑怎么做我们分成两步，第一步把\sum\limits_{i=0}^n i^m变成一个m次多项式，第二步用第二类斯特林数。第二步是简单的，考虑第一步，我们发现拉插并不管用，所以使用NTT，我们发现NTT所需的若干点值带入时，我们可以使用等比数列求和快速做，然后IDFT回去就好了。

然后我们有

于是就好了。

1009

简单题，注意题目有没有给出父亲标号比儿子小。

1010

相当于两个问题，一个是子树选两个数xor最大值，一个是去掉一个子树选两个数xor最大值。第一个可以字典树+启发式合并2log，第二个可以先找到对于整棵树xor最大的两个位置，那么答案不是它们xor的，一定是包含了其中的一个，具体就是在它们到根的路径并上，由于是两条路，可以直接字典树暴力加点，每个点只会加一次。

1011

考虑割边显然不能断，取一个min。仙人掌的话显然时刻有n-1个边是充要的，那么就是min(w1+w2,w3)，其中w_i是第i小。

1012

简单题。

2023“钉耙编程”中国大学生算法设计超级联赛（6）

1001

就是border转周期后直接快速幂。

1002

我们可以暴力扫，然后暴力加入，用树状数组维护，考虑只有O(\sqrt n)对，所以是对的。

因为只有O(n\sqrt n)次加入，O(n)次查询，所以可以值域分块来平衡复杂度去掉logn。

1003

我是用单纯形板子的，std不想了解。

1004

我们算出三种颜色个数x,y,z，我们把x-=z，y-=z，那么条件等价于x=y=0，用点分治+map解决即可。

1005

我们考虑可以求出以每个点为左上端点的最大的L，然后考虑就是若干i从1-L变，然后左上端点固定，所以矩阵查询改成前缀和的差分，通过对一行，一列，一对角线打标记来得到对于每个前缀和的贡献，然后发现是加上一个等差数列，可以二次差分。

1006

我们考虑对于每个点算出跨过它的区间在它的不同取值下，分别有多少个，我们可以枚举每个点，然后枚举跨过它的区间[l,r]，我们计算出所有的s_r-s_{l-1}-a_i，然后放到桶里面，然后我们枚举i的取值，枚举合成的平方值，然后在桶里面查，一共O(n^3)。

1007

二分套数据/cf/cf/cf。暴力过/cf/cf/cf。

1008

被坑了，对于一些题目，可能SG是不好做的，维护必胜必败是好做的。这里我们就像every SG那样，算出必胜必败和值，然后我们一起做，对每个左右端点和必胜必败开一个单调队列维护值，然后直接转移即可。

1009

1010

倍增算即可。

1011

2023“钉耙编程”中国大学生算法设计超级联赛（7）

1001

我们考虑由于有断边和另一种操作，所以不可以直接时间倒流。

所以考虑直接断边，这里有一种类似启发式的方式。

考虑对于每一个连通块维护一个线段树维护每种颜色的次数，和一个并查集维护每种颜色变成了什么。考虑二操作，就可以暴力在对应的线段树里面抽出含有的颜色，同时在线段树里面把这块清了（ls和rs归0），之后线段树上单点加，并查集暴力连。对于三操作，暴力查询。对于一操作，考虑启发式，暴力查出小块每个点的信息，在大块的线段树和并查集上把小块信息去了，同时构建小块线段树和并查集。一共O(nlog^2n+mlogn)。

1002

结论简单，就是一旦有>1的，答案就是499122177，否则是0或1。

1003

考虑(1234),(1235)生成S5，同理的，S7，S8也可以生成，所以用并查集维护置换，如果大小不是4或6，那就是任意置换，否则如果是4，那么是(1234)生成的群，如果是6，那么就是(1234),(3456)生成的群，直接做。

1004

可以构造类似131313221313132的，然后发现与暴力打表的前几项是符合的，然后说明这种构造是合理的。

1005

我们考虑对于当前串，尝试加入'a'-'z'，我们同时维护当前subsequence和substring的最左的末尾x和y。考虑如何尝试，我们可以得到x'和y'（实现的时候存的是sam上的节点，但是可以对于每个sam节点得出最靠左的位置），如果不存在y'，那么久直接加入这个然后输出答案即可。如果存在那么我们考虑，如果有x‘!=y'，那么我们之后把x'之后的全选就是一种合法方案，直接递归下去。否则，首先，我们一定在x'之后选尽量多元素，假设后面有p个，那么就选p-1个。接下来考虑两种情况，如果当前字符串不是同一个字符，那么我们发现用位置靠后的substring是无效的，因为长度都不够了，然后我们接下来x'之后选最后p-1个，那么相当于如果非法，那么x'的后面有一个长度p-1的border，所以就是x'后面字符全部相同，这显然是紧的界。如果当前字符串是同一字符，那么可以发现一个结论，就是如果下一个还是这种字符那么可以不断向后跳一格，然后直到不能跳，后面的一段都相同那么非法，证明是容易的。

1006

1007

1008

简单题，注意细节。

1009

1010

1011

贪心的选三个中的一个，暴力几次后，就一直是-1操作了。

1012

建立点分树，然后用个线段树做即可。也可以用有序序列+扫指针代替线段树。

1013

可以证明如果2^i<=n，那么存在一种操作方式使得可以任意的反转第i位，除了i=1的情况。那么我们用树状数组数逆序对，就知道二进制下第2位是0还是1，其他位暴力一遍即可。

2023“钉耙编程”中国大学生算法设计超级联赛（8）

1001

多项式，不会。

1002

计几，不会。

1003

考虑一个更加松的命题，对于每一条式子，把%n改成%pi，那么就可以化简成x \equiv q_i\ mod\ p_i，所以就可以使用CRT。然后发现这样子在n以内只会解出一个解，所以只要带回严命题验证即可，若不对，那么就是无解。

1004

线性基+bitset，比较朴素，略。

1005

考虑最优策略是怎么样的。

分三类：

两边都不是我的，那么输。

一边是我的，那么只能取那一边。

两边都是我的，如果有一块的大小>1，那么我赢，否则如果有至少一侧向内一个是一个大小为1的对手的块，那么我取这个之后对手只能取这一个，然后就回归了状态，所以如果至少有一个向内是大小为1，那么就优先取这个，否则说明两边向内的大小都>1，我必输。

1006

考虑对于每一个点求出和T1的最长公共前缀和最长公共后缀，那么我们枚举l和r，使得s[l,r]与T1和T2的合并串匹配，那么就可以知道T2的插入位置可以由上面求出的最长公共前缀和最长公共后缀来限制位置，那么就相当于询问s串的一个区间中T2出现了几次，可以开始时KMP求出。

1007

简单题。

1008

考虑dp，设f_{i,j}表示i个向量，秩为j，那么有f_{i,j}=f_{i-1,j}+p^j表示新的还在这个空间中，以及f_{i,j}=f_{i-1,j-1}+p^n-p^{j-1}表示新的与之前的线性无关，然后就可以转移处理了。

1009

考虑这个是可二分的，我们来找一个快速判断的充要条件。首先我们要满足如图的折线互不相同，这个可以对于每个点记录最近的相同元素出现位置来预处理，对于每个左下角都处理出能延伸的最远右上角。还有一个，就是要满足斜线相同的性质，如图，我们可以对于每一个左下角处理出向右上最远可以延伸的地方是的每个斜线都是相同的，具体的如果a_{i-1,j}==a_{i,j+1}那么f_{i,j}=min(f_{i-1,j},f_{i,j+1})+1，证明显然，否则f_{i,j}=1。我们对于每个右上角也处理一个类似的东西，然后就可以左下角掌控一个下三角，右上角掌控一个上三角，分别判断了。

1010

考虑d=abs(a-b)。

如果d是平方数，那么答案是1。

如果d!=2k（k为奇），那么d就可以拆成两个奇偶性相同的数之积，具体是d=(a+b)(a-b)，答案为2。

否则，我们暴力判d能否变成两个平方数之和，这是O(\sqrt d)的，如果不能，那么可以先d--，那么d就变奇数，可以拆乘积了，答案是3。

2023“钉耙编程”中国大学生算法设计超级联赛（9）

比赛出的不错，但是我打烂了。

1001

1002

考虑dp，这是一个形如变进制数的东西，f_{i,j}表示当前这位一位就表示2^i3^j，然后f_{i,j}向f_{i+1,j}和f_{i,j+1}转移即可。

1003

好像又是考查审题的题目，审完题好像就水了。

1004

1005

简单题。

1006

1007

1008

结论题，ans=\sum_{i<j}a_ia_j，不想看证明了，好像需要停时定理。

1009

1010

1011

考虑容斥，我们用一系列的大小为cnt，权值为-1的物品做背包，那么每一项就对应了容斥系数。考虑怎么加速背包，对于cnt<\sqrt \frac{n}{logn}的，我们可以O(n)处理出对于不同cnt的f数组，然后把它们卷在一起，一共O(n\sqrt {nlogn})，对于其他的暴力做背包，由于\sum cnt=n，所以也是O(n\sqrt {nlogn})。容斥系数求完之后随便算下组合数就好了。

还有O(nlogn)的多项式解法，不想看。

1012

题干抽象，其实就是一个高精或者log化积为和的板题。

2023“钉耙编程”中国大学生算法设计超级联赛（10）

哎，这场真的是打坏掉了，无语，T11想出来了但是脑抽规律找错了，哎。。。

1001

1002

1003

考虑先以a为标号建树，然后再把原排列以n!标回去。

1004

题叕看错了，无语，白推了1h推出错误version的解法，读对了之后发现答案就是(2n-1)/3，在场上是推出来的，这里现在没心情写过程。

1005

1006

1007

1008

题目叕叕叕看错了，看成区间xor了，简单题，压到线性基里面，然后不够的用0补全，然后check一下是否合法即可。

1009

简单题。

1010

1011

我们把它们分成m组，然后用坐标(x1,x2,……)表示一个位置，我们把第一维去掉，变成(x2,……)，然后x1=n-1-x2-x3-……。考虑每组怎么标号，我们发现对于(x2,……)（这个是x1=n-x2-……），它去掉每一个位置后会形成(x2,……)和(x2-1,……)，(x2,x3-1,……)等。那么我们让前面所提及的第一个标号为1，之后顺次标下去，我们让标号1的赋值为1的组，在位置2赋值为2，在位置3赋值为3等等。那么对于这一组，无论它接受到的信号是什么，都可以选对。然后我们看一下这个相当于是什么，发现就是在坐标系里面行走，如果对于两个相邻位置x和y，如果x=(x2,x3,……)，y=(x2,……,xp,……)，那么y的组赋值就是x为p的组对应位置赋值为1，其他都没有要求。然后手玩一下发现其他位置有性质就是相对顺序还是1,2,3,……，只是转了一下，这样子可以保证勾勒出所有点，所以我们就在坐标系里面bfs，然后后继的1通过当前的赋值确定，剩余位置依次标下去。具体可以看代码，讲的比较抽象。

1012

简单题。