本题题意：给出长度为n的序列a，表示每个点成功的概率，从1到n的分数计算方法是，若成功则获得连续成功的长度的m次方的分数，求最后的分数期望。 解法：咋看像是一个概率DP，实际上在支持n^2复杂度的情况下，我们只需要计算出所有单段连击的期望，然后求和就可以得到总的期望分数。 首先，预处理出每一段一直成功的概率。 然后我们可以枚举i,j表示在[i+1,j-1]区间内成功连击，并且由题目可知要计算上这段分数必须在i,j失败，结束连击，这段的期望就是(i失败的概率)*(j失败的概率)*([i+1,j-1]都成功的概率)。 为了方便计算，我们可以把0,n+1两点的成功概率...

大概题意：给出一个由大小写英文构成的n*m矩阵，问有多少个子矩阵满足每行每列没有重复元素。 题解：首先我们知道 总共有52个字母 所以我们可以用52位的二进制表示有哪些字母出现过，每行每列用一个状压值表示元素，来保证可以快速判断一个新加入点的元素在纵向和横向是否冲突。 简单可知我们只要找到以每个点作为子矩阵左上角，对应的合法右下角点个数总和，就是我们要的答案。 对于第一列做如图操作 每一行向右遍历找最长可达到的点，直到一行合法长度为0停止。这样我们就找到了1️⃣第一列第一行的贡献。 然后我们再去求第一列第二行的贡献，此时我们分别在横纵的状压值上删去第一行，然后接下来在之...

题目大意是给出一个式子an 求其前n项的和。 首先我们可以发现 在n mod4 为0、3时 an=a[n/2]+1,n mod4为1、2时an=a[n/2]-1。 而从a1到an要经过log2 an次这样的加减，可以转化成二进制位上的问题。 把n化为二进制数组b,当某位bi与bi-1组成的二进制为0、3时+1，为1、2时-1，例如bi==1,bi-1==0，二进制就是10，十进制为2，此时-1。 此时我们就可以在log复杂度内求出an。 然后我们再利用数位dp,来求出前n项的和。 dp存储的第一维len表示位数。 第二维 if ...

题意：     给一个字符串 将这个字符串从每个字符为起点的串分类输出 例如abab 它的串分别为abab baba abab baba 于是输出两种 abab的两个串起点分别是0、2，baba的是1、3。 解法：     首先我们可以观察到，每个串的长度都是相同的。我们只要找到这个字符串的最大循环节长度maxlen，就可以知道有maxlen种串，然后按照循环直接输出每种串的每个位置。     这个时候很多人用了kmp，但是这个题其实是可以用更简单的方式来找出这个循环节。最大循环节长度maxlen显然必须可以被字符串长度len整除，所以必然是len的因子，而字符...