分类： 数学

2019 ICPC南昌邀请赛网络赛 K MORE XOR

题目链接

(⊙﹏⊙)不知道为什么比赛时候这个题和D题死推不出来，比赛完了5分钟ac，我大概脑子坏掉了。真的是超超超超级简单的一个题，但是我光顾着用数学公式推了所以推出来结果巨复杂(⊙﹏⊙)服了自己了。

题解：先说怎么求g(l,r): 首先f(l,r)很好求，利用异或的性质，预处理出来前缀异或和就可以了。设预处理出来p1[x]表示从a[1]到a[x]的异或和，那么很容易得到\[f(l,r)=p1[l-1]\oplus p2[r] \], 那么可以由g的定义就可以知道 \[ g(l,r)=\sum_{i=l}^{i=r} \sum_{j=i}^{j=r} f(i,j) =\sum_{i=l}^{i=r} \sum_{j=i}^{j=r} p1[i-1]\oplus p1[j] \];当然这个东西还是很复杂的，我们想办法把他复杂度搞到O(1)：考虑每个p1[x]出现的次数，列个表可以发现，在这个求和式中出现的所有下标，从l-1变化到r, 而每个下标出现的次数都是一样的，这个次数等于 r-l+1 ，那么就可以得出结论，如果r-l+1为偶数，则g(l,r)应为0，否则应为\[ \sum_{i=l-1}^{r} p1[i] \]，注意到这个式子又可以用p1的前缀和来O(1)计算，所以又可以提前求出来p1的前缀和p2，这样的话g(l,r)就可以表示为

\[g(l,r)=
\begin{cases}
0& \text{(r-l+1) is odd}\\
p2[l-2]\oplus p2[r]& \text{else }
\end{cases}\]

有了g(l,r)再来考虑w(l,r)，\[w(l,r)=\sum_{i=l}^{i=r} \sum_{j=i}^{j=r} g(i,j) \],就跟g的表达式很像，但是这里不能直接再套用g关于p1的公式，因为g里面有很多的0是跟p2无关的，换句话说这些0并不是由p2[l-2]^p2[r]求出来的，所以要分类讨论。分析方法跟g是类似的，列一个表观察每个p2出现的规律，可以发现，这个规律是4个一循环的结构，设\[t=（r-l+1)\mod 4\]; 则当t==0时，所有的p2下标出现次数均为偶数次，也就是结果一定为0，t==2时，所有的p2下标出现次数均为奇数，这样的话即等于\[\sum_{i=l-1}^{r} p2[i] \]，这个式子说明我们可以再用一个p2的前缀和p3来O(1)计算这个结果。这是比较简单的两种情况，另外两种是t==1和t==3，这两种一种是奇数项的出现次数为奇数偶数项为偶数，另一种是奇数项出现次数为偶数而偶数项出现次数为奇数，这意味着可以用一个分奇偶的前缀和来O(1)求得这个式子只不过仍需要分类讨论一次。。若令p31[i]和p32[i]分别表示p2的奇偶前缀和，t=(r-l+1)%4, 则w(l,r)的表达式为

\[
w(l,r)=
\begin{cases}
0& \text{t=0}\\
p31[r]\oplus p31[l-3]& \text{t=1 and r is odd}\\
p32[r]\oplus p32[l-3]& \text{t=1 and r is even}\\
p3[l-3]\oplus p3[r]& \text{t=2}\\
p32[r-1]\oplus p32[l-2]& \text{t=3 and r is odd}\\
p31[r]\oplus p31[l-3]& \text{t=3 and r is even}
\end{cases}
\]

这样的话整个问题就可以O(1)解决了。。不知道我当时脑子怎么回事就没推出来
继续阅读“[比赛补题][×] 2019 ICPC南昌邀请赛网络赛 K MORE XOR”

题目链接

这个题一开始想歪了一直在想polya。。。带了半天队友节奏最后俩人都没整出来。

其实一开始就不该被给出的示意图带着走的，当时已经想到了剩下的是n-m段，但是关键在于没有想到怎么处理排列的去重。。。试了下用母函数分配出入度后来发现无法去除已经有圈的情况于是放弃。。其实这时候该想想能不能换个方向用母函数，哎，总的来说还是太菜，做组合数学还是不行。

后来想了下，可以先完全去掉所有的标号，也就是说把所有的点当成同一种点，然后去解决把这n个点分为n-m条链的分法，最后把标号还原回去只需要乘以一个n!的全排列系数就好了。

这时候问题转化为n个相同的点，分为n-m个链条（单个节点自身也是一个链条）的分法，而且这种分法要考虑到空间对称（参考样例）。我们可以设普通型母函数\[F(x)=a_0+a_1x+a_2x^2+…+a_nx^n\]来表示一条链的情况，幂次等于这条链条有多少个节点。由于不认为0个节点是一个链，所以\[a_0=0\], 然后当节点数多于1的时候由于空间对称要除以2，所以除了\[a_1\]之外所有的a都是1/2，也就是说对于一条链其母函数就是\[F(x)=x+1/2 x^2+1/2 x^3+1/2 x^4+….+1/2 x^n\]

得到了一条链的F(x)，由母函数的性质可以得到k条链\[(k=m-n)\]的情况就是\[F(x)^k\]的结果中\[x^n\]的系数，只不过还要乘以一个\[n!\]的系数（因为我们之前把所有球都当作一样了所以要乘以一个全排列）再除以一个\[(n-m)!\]（因为每次算出来的是所有可能的组合情况，但是这k条链条是不用排序的）

现在的话就是如何计算\[F(x)^k\]的结果中\[x^n\]的系数了，直接暴力肯定超时，考虑把\[F(x)\]的函数变换成更简单的形式。由级数的知识可以知道|x|<1时，\[ F(x)=（x-1/2 x^2)/1-x\] , 那么\[F(x)^k=x^k(1-1/2 x)^k/(1-x)^k \],\[x^k\]好处理，这说明只需要求剩下的部分的\[x^(n-k)\]的系数就行了。看剩下的部分，这里的分母看上去很难操作，但是可以再用级数的方式变换一下 \[1/(1-x)=(1+x+x^2+x^3+x^4+…+x^n)\], 也就是说要求的部分变成了 \[(1-1/2 k)^k (1+x+x^2+x^3+x^4+…+x^n)^k\], 后面的这一坨\[1+x+x^2+x^3+x^4+…+x^n\]可以认为是一次一次乘到前面的。前面的\[(1-1/2 x)^k\]可以用二项式展开，每一项为\[C_k^{i} (-1/2 )^ix^i\] 。这时候考虑计算“二项式展开中第i项对于最终结果的第j项的贡献度(i<=j)”，可以想象一下i变成j是因为加了j-i个1次幂，而总共后面乘的是k个多项式，那么所有的情况也就是中学常学的“把j-i个物品分成k份允许有空集的分法”组合问题了，答案是\[C(j-i+k-1,k-1)\]，当时高中数学老师管这叫插隔板法还是什么来着emmmmm。这时候就容易计算了，在算贡献的时候再带上（-1/2）的i次幂就行了。。。

确实是不好想，尤其是在现场赛的环境下，感觉自己还是得更多的做难一点的题目。

继续阅读“[数学][组合数学][母函数][比赛补题][×] ZOJ 4069(2018 青岛现场赛 L) Sub-cycle Graph”