高度由习惯堆积

2019年2月

February 24, 2019

AC自动机初步

概述应用场景:多模字符串匹配问题。KMP解决的问题是两个字符串之间的互相匹配,而如果有多个字符串要和一个字符串进行匹配呢?如果还用KMP的话,复杂度依然上天,所以,一个正常的想法是在KMP的基础上堆数据结构。所以AC自动机=在Trie树上跑KMP,它其中也存在失配数组,与KMP类似。初见AC自动机的基础是Trie树。和Trie树不同的是,树中的每个结点除了有指向孩子的指针(或者说引用),还有...

HDU6155 Subsequence Count

题目给出一个长度为n的01串S,有Q个操作:1.翻转区间[l,r](0变1,1变0)2.求区间[l,r]有多少不同的子串思路这是一道好题,首先考虑没有修改操作的dp状态,则$dp[i][j]$表示到了第$i$个位置,结尾为$j$的串的方案数则我们可以得到以下递推关系:$$ dp[i][j]=dp[i-1][0]+dp[i-1][1]+1,j==S[i]\\ dp[i][!j]=dp[i-1]...
February 17, 2019

HDU5564 Clarke and digits

前置知识$dp[i][j][k]$表示$i$长,$mod7=j$,这个位置选了$k$的方案数。$dp[i+1][(j*10+x)mod7][x]+=dp[i][j][y];//x+y!=K​$$Ma.a[i][j]=1$表示$i$状态->$j$状态可以转移如果设$ans=qkpow(Ma,K)$。则$ans.a[i][j]$表示走$K$步之后状态$i$到状态$j$的方案数。如果对这个不...
February 17, 2019

ZOJ3822 Domination

题目Edward is the headmaster of Marjar University. He is enthusiastic about chess and often plays chess with his friends. What's more, he bought a large decorative chessboard with N rows and M column...