思路比较简单但是很经典的一题，最近一直在补数学。。
用dp(u)表示以节点u为根的种类数，则由基本的组合数学可以得出\[dp(u)=(\frac{(n-1)!}{\prod size(v)})*\prod dp(v),\ u\ is\ v’s\ parent\] 其中\[size(v)\]是以v为根的子树的大小。然后由于这里模值是任取的，所以不能用求逆元的方式来做，否则的话也太简单了。
考虑进一步化简这个式子，把\[dp(v)\] 们展开（脑海中展开）可以发现对于每个节点来说，他以 \[(size(v)-1)!\]的形式出现在分子上一次，以\[size(v)!\]的形式出现在分母上一次，所以最终把所有节点（不仅仅是root的直接儿子）全部代进去就可以得到\[dp(root)=(\frac{(n-1)!}{\prod_{v=2}^{v=n} size(v)})\]
继续阅读“[组合数学][大组合数取模][TreeDp] UVA 1436 Counting heaps”
这个题一开始想歪了一直在想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”
简单分析易知如果Yes的话整块巧克力一定是从最初的一大块不断地分成矩形来实现的，而一个矩形分成两个小矩形的方法只有两种，横着分或者竖着分，这样的话就可以枚举断点分割，大问题转化为小问题递归解决。然后总共的小块数量最多15，很明显可以用二进制表示获得的块的状态。但是直接定义类似\[dp(r,c,S)\]这样的状态会造成\[O((x+y)xy2^n)\]的复杂度，基本上不能通过这个题（其实做了极致的优化的话时间上应该可以做到但是空间复杂度会超过2GB）。然后考虑状态的进一步化简，可以发现实际上如果确定了S，则可以通过r和c中的一个计算出另一个（或者发现根本不存在这样的数），由此只需要考虑\[dp(r,S)\]即可，其中r是原状态r，c中较小的那一个。另外，枚举分割点时间是并不优秀，因为还得检查当前集合是否支持这样的分割，不如直接枚举所有的子集分割情况，然后用这个来算出分割后的子函数的r和c。按照计算矩阵链乘的方式来做复杂度分析可以算出时间复杂度\[O(x3^n)\]。直接记忆化搜索的话，会比这个上限要小得多。
继续阅读“[状压DP][枚举子集] UVALive 4794 Sharing Chocolate”
我为什么要写个这
需要的工具：科学上网工具，一般是ss或者v2ray
首先到官网下载安装Tor Browser
安装完成后打开，点configure设置
对windows用户来说，设置成如下界面情形即可。linux的话道理是一样的，菜单界面稍有不同（推荐最好使用Linux）
又是一个Trie图上找递推关系的题~只不过这次是单字符串做一个Trie图（这样的话用扩展kmp也可以8
把样例研究一下再结合Trie图基本就能确定出等式关系了，设dp[i]为
现在在Trie图上的节点i，还需要走多少步（期望意义下）才能凑出给定的字符串
容易知道当走到尽头的时候dp[n]=0;其他的项地推关系可以表示为dp[u]=1+\sum i/n*dp[v] ,其中v是u走向的下一个节点。
以样例n=2,s=”ABA”为例，Tried图和方程组如下
解这个方程组可得dp[0]=5,就是我们要的结果了。
具体代码实现的时候，直接对每个结点都把转移记录下来，然后用高斯消元解方程即可。注意应该把n乘到等式左边，然后用整数的高斯消元，不然会有误差wa。
继续阅读“[AC自动机][Trie图][期望DP][高斯消元] Generator UVALive 3490”
题目链接： Password Suspects
这题让我回想起了某现场赛被某大佬支配的恐惧
感觉是dp，而且这个子串的数据量一看就是状压，然后在推转移方程的时候死活推不出来一个不交叉的。可耻的搜了题解，看到大佬们的标题：AC自动机+DP
我就
~~其实是常见的一种操作只是我太久没做过字符串的题目了~~
在思考递推方程的时候就一直在纠结前缀与后缀重合的这种情况怎么表示状态，然后忽然意识到ac自动机（更确切的说是Trie图）就是可以唯一的确定一个匹配状态的数据结构！这种题一般都是给定一些字串，然后给出一些约束条件，比如要求
题意：给出n个字符串，要求求出所有的前后缀组成的字符串种类数。
思路：比较简单的一题。 用Trie存储所有的字符串，可以算出所有不同的前缀数，然后把字符串全部反向再插入到另一个Trie，得出所有的后缀数量。二者相乘可以得到所有的可能结果，但是会有重复，所以要去重。去重也很简单，画一画样例可以看出来一定是算出来两个Trie里面的相同的字符出现的次数，每一个字符结点出现一次就会有一个重复，这样减去所有的重复即可。但是直接这样算会有错误，因为可能会产生有的前缀为空后缀为一个不完整字符串，这样是不满足题目要求的，所以在统计结点数量的时候只统计长度大于1的结点（在Trie里深度大于1），然后这样构造出来的全部是满足要求的字符串而且没有重复，但是仍然有一个bug是有的字符串只有一个字符，而上述方法是只能构造出来最小长度为2的字符串的，因此要另外处理这些长度为1的字符最后加到答案里。
试了很多网上搜到的方法，类似于qq邮箱app申请，ie浏览器申请，之类的都不行了，然后拿自己的旧手机试了试，成功了就分享下（上面我的YouTube视频
其实就是用旧版本的安卓手机上的gmail app申请了，不过google对gmail申请限制也越来越严了，不知道这个什么时候会失效。
题目特殊的地方在于运算是异或，不是像经典的带权并查集那样可以有一个恒定的子节点与父结点的递推关系。比如传统的求一个结点到根结点的距离的并查集可以这样写
int findfat(int x)
{
if(fat[x] == x) return x;
int tmp=fat[x];
fat[x]=findfat(fat[x]);
//在此处修改val比如：
value[x]=value[tmp]+1;
return fat[x];
}
这样写的正确性在于这个递推关系一定是正确的，即使在森林里改变任意一个点的数值，在他的后代执行findfat的时候也一定能更新所有的数值。但是异或是不太一样的，如果直接写 value[x]=value[x]^value[tmp]，的话，仅仅是对x求两次查找根结点而不做任何其他操作就会使得数值出现错误，因为w[x]等于和自己又异或了一次，就会出现不正常的结果。
思考了一下，我直接把w数组定义为：w[i]表示 继续阅读“[数据结构][带权并查集][异或] UVALive 4487 Exclusive-OR”
这几天闲着没事干，看到自己站点每次在chrome里打开左上角显示不安全就感觉很不爽，于是乎想搞个ssl证书用https，可是没想到这一搞就搞了一下午。让这件事变得很tough的原因主要是。。。
我当时建站的时候用的是腾讯云的一键安装，他这个自动程序搞出来的结果和正常的自己手动安装的标准流程很多地方不一样，导致我无论是找文件的位置还是设置用户还是设置端口都很头疼
网上各种讲教程的博客，时效性太差，很多命令和软件包早已失效，照着做下来各种报错
首先选择一个ssl证书，这里我当然也是选择了免费的Let’s Encrypt。之后就开始参考各种博客来装，基本上他们讲的都是用certbot来装，一条命令yum install certbot，但是我怎么操作都是显示没有软件包，一开始以为是软件源的问题，后来装了个各种依赖，换了阿里的源还是不行，然后就google了半天挖出来一个不用certbot的方法。
他这里讲的要先把python升级到2.7，不过我没升级也成功了。首先获取letsencrypt
继续阅读“centos6.9上的wordpress站点添加ssl证书踩坑记”