Believe it

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 链接http://acm.hdu.edu.cn/showproblem.php?pid=5745

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 给你一棵n个节点的树，要你求出包含每个点的连通点集的数量。答案对1e9+7取模。 两次dfs，第一次处理每个节点的子孙方向的联通点集数量，$$dp[i]=\prod _{all..son}{(dp[son]+1)}$$ 第二次处理父亲方向的点集数量$$\begin{aligned}&dp2[i] \=&(\prod _{all..brother}{(dp1[brother]+1)})*dp2[father]+1 \=&\frac{dp1[father]}{dp1[i]+1}*dp2[father]+1 \\end{aligned}$$ 特别注意这里小心没有逆元

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 12345678910111213141516171819202122232425262728293031323334353637383940struct Manacher {//鉴于马拉车算法较复杂，此处有少量修改， //s[i]=ma[i<<1] //mp[i]表示以i为中心的最长回文串的半径，且mp[i]-1恰好为此回文串包含原字符串的字符的数量 //可以证明ma字符串所包含的回文串总数=原字符串b所包含的回文串总数+2n+2 static const int maxn = 1e6 + 666; char ma[maxn << 1]; int mp[maxn << 1], begat[maxn];//begta[i]-> 以i开头的回文串的数量 begin at void build(ch ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial AC自动机所谓AC自动机，其实是kmp算法与字典树的结合,不懂这两个，是无法学会的。 自动机自动机，是一个五元组，包括了状态的非空有穷集合，符号的有限集合，状态转移函 数， 开始状态，终止状态集合，而在字典树上，增加了两个新的东西，一个标记了终止状态集合，另一个辅助了状态转移函数。 我们利用字典树上 的节点来表示状态，而边则用来表示状态转移函数的一部分。 匹配当AC自动机建立好了以后，我们就可以在AC自动机上进行匹配了，我们在自动机上一 个一个 节点忘下跑，一直到失配，即到达AC自动机上某个节点后，此节点所代表的字符串，与母串的当前前缀子串相差刚好只为最后一个字母，这 时候，我们跳跃到fail指针即可进行后面的继续匹配。 file指针fail指针当然跳得越深越好，这时候fail所代表的意义到底是什么呢？很明显，此时 要求与母串有 尽可能长得公共前缀，也就是说与失配发生的时候AC自动机所在节 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 回文自动机，就像AC自动机一样，他采取字典树来储存状态集合，也像AC自动机是KMP 算法与字典树结合一样，回文自动机就是manacher算法和字典树结合的新算法。 在回文自动机里面，状态指的是，以字典树上所表示的字符串的逆序串的以末端字符镜像对称后得到的新串,简单说，baab在字典树上为root->a>b,cacaacac在字典树上为root->a->c->a->c,想像根就是对称中心，往儿子走就意味着，在对称中心两端加上同样的数字。当然这样子是无法表示奇数回文的，所以我们设立两个根就可以了。一个串的回文自动机，储存了这个串的所有回文子串。 回文自动机的状态转移的依据是回文，举个例子，如下图，如果黑色串代表以黄色字符为结尾 的最长的回文串，红色串代表黑色串的最长真后缀回文串，（定义：若回文串a为某串b的真后缀，则a为b的真后缀回文串，定义：若后缀a为某串 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial codeforces 1043B 本质上让你求一个字符串可能的循环节，题目的第二个样例可以看作求序列 1，2，2，1，2，的循环节显然可以是3或5， 于是算法出来了，我们只要求出最小的循环节就可以了，最小的循环节怎么来求呢，我们hash预处理原字符串以便后面O1查询区间hash值，对于字符串s如下图，我们对原字符串复制一份，错位比较红色竖线之间的子串，如果相等，意味着什么读者可以自行思考，于是我们已经找到了On的做法了，我们只要从小到大枚举 蓝色区域即可

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 定义： 先定义一个字符串s，假设它的长度为n，s[i]表示第i个元素 ，s[i…]代表以s[i]开头且包含s[i]的后缀。我们定义新的数组 sa[i]为一个0-n的排列，且sa[i]为后缀s[i…]在所有后缀中按 照从小到大排序的排名。最后定义rank是sa的反函数。 sa数组也称为后缀数组 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465//定义以s[i]开头的后缀是suf(i)//后缀数组性质：suf(sa[i])<suf(sa[i+1])//模版从下标为1的地方开始，引入的字符串下标也要从下标为1开始struct SA{ static const int MAXN=2e ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 题目12018宁夏网络赛H题 给你类似剪刀石头布游戏的五种手势和十种克制关系。每种手势克制其他两种手势并被另外两种手势克制。给你两个字符串分别表示A，B的 手势顺序，A长B短，你可以随意挪动B相对于A的位置，求B最多能赢多少次？ 1234567891011若两个串为abcde和ede则共有三种方法来决斗，abcdeedaabcde edaabcde eda为每一个字符标上指数，将一个串逆置后，发现是fft 题目2 BZOJ4259 给你两个字符串原串和匹配串，串里只包含小写字母和∗,∗可以表示任意字符，问匹配串在原串不同位置中出现多少次，起始位置不同即不同位置。 我们还是利用上一题逆置短串构造卷积的方法，我们把*的值当作赋为0，pow(str1[i]−str2[i],2)*str1[i]*str2[i] 化简消去负数项即可 FFT1234567891011121314151617 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 这是我自己给这类图取的名字 给出定义， 有五类边 第一类为原点到左边的点，容量无穷大,有费用 第二类为左边的点到右边的点，一对一，容量为任意常数，费用0 第三类为右边的点到汇点，容量无穷大，费用0 第四类为左边的点依次连i->i+1，容量无穷大，费用0 第五类从右边连向左边，容量无穷大，费用0 如下图左边的图 给出问题,求当有容量的边的都满流时的最小费用 我们发现左图的最大流一定满足有容量的边是满流的，我们尝试将其转化为最小费用最大流 我们发现，如果我们对左边的图跑最大流，当左边的图有流量进入y点集的时候，他一定会进 入源点，不会流回x点集，这就很烦，我们要的不是最大流，而是指定边的满流，我们尝试“阻 止”这个过程，怎么阻止呢，我们在考虑一个z点集，从源点出发，每当y点集有流量流入汇点，就从源点流等量流量到对应的z点集，我们最后用z点集完全替代y点集的回流功能，这样以 ...