前言这是一篇分块题解，大概的思路洛谷的题解里的巨佬讲的很清楚（我的思路其实和大佬的差不多），可以去看看qaq。因为苯人为了卡常魔改代码，所以在本题解的中间具体步骤展示部分仅展示魔改前的代码（也就是被卡常但是好看一点的代码），魔改后的代码（100pts）在文章最末展示。题意题面传送门

https://www.luogu.com.cn/problem/P1972莫队算法被卡，只能得60points正解有点像基于贪心的fenwicktree策略fenwick的每个位置表示当前位置上是否是某个数的最后一次出现位置，值为0或者1右指针升序排序，然后右指针移动过程中更新每个数最后一次出现的位置而不管左指针如何变，只

[SDOI2009]HH去散步设\(dp_{i_j}\)表示第\(i\)个时刻，走到第\(j\)条边的终点的方案数转移：从当前点\(u\)开始，枚举从\(u\)出发的所有点，向\(dp_{i+1,to_u}\)转移但是\(t\)非常大，所以需要使用矩阵快速幂设初始矩阵为\(\text{A}\)，转移矩阵为\(\text{B}\)，那么答案矩

P2167[SDOI2009]Bill的挑战状压dp/二项式反演先说状压，考虑怎么刻画\(S\)和\(T\)匹配这个东西。实质上就是从前往后匹配每一位，直到哪一位不匹配了，那么就不匹配，也就是每一位字符匹配的并集。同样，对于多个串的匹配，设第\(i\)位字符为\(j\)时匹配的串集合为\(g_{i,j}\)，对

[SDOI2009]Bill的挑战题目信息题目描述Sheng_bill不仅有惊人的心算能力，还可以轻松地完成各种统计。在昨天的比赛中，你凭借优秀的程序与他打成了平局，这导致Sheng_bill极度的不满。于是他再次挑战你。这次你可不能输。这次，比赛规则是这样的：给出\(N\)个长度相同的字符串（由

每个点拆成入点和出点。发现每个点、每条边都只能经过一次，所以所有边的容量都是\(1\)。#include<bits/stdc++.h>#definelllonglongusingnamespacestd;constintN=405,M=1e5+5;intn,m,s,t,k=1,h[N],vis[N];intto[M],nxt[M],w[M],f[M];intlst[N],flw[N],dis[N];v

[SDOI2009]Bill的挑战题目描述Sheng_bill不仅有惊人的心算能力，还可以轻松地完成各种统计。在昨天的比赛中，你凭借优秀的程序与他打成了平局，这导致Sheng_bill极度的不满。于是他再次挑战你。这次你可不能输。这次，比赛规则是这样的：给出\(N\)个长度相同的字符串（由小写英文

[SDOI2009]HH的项链题目描述HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此，他的项链变得越来越长。 有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同

传送门简要题意：有\(n\)个人，\(m\)条无向边，走\(e\)条边，满足条件若第\(i\)条边为\(u->v\)则第\(i+1\)条边不能是\(v->u\)，问\(s->t\)的方案有多少个，取模45989。因为要满足题目关于边的条件，所以我们考虑点边互换。将\(u-v\)的无向边一分为二变成\(u->v,v->u\)，第\(i\)条边记录两个变

题目链接题意简述：求两条给定起点终点最短路的最长公共路径。首先最长公共路径一定是两条最短路的公共最长链的部分。至少一定在两条最短路上。考虑如何求出一条路径是否包含于一条最短路，只要路径\(x\rightarrowy\)满足：\[dis_{st\rightarrowx}+w_{x\rightarrowy}+dis_{y\r

题目链接对于这类问区间不同数的总数，显然是不能用线段树直接维护的，毕竟不符合区间区间可加性。考虑对于一个右端点固定的询问，哪些数字实际上是有权值的。比如区间1332312，显然，实际上对于相同的数字，只有一个是有权值的，其他权值均为\(0\)。但是这样还是无法起到简化的作用

[SDOI2009]Bill的挑战目录题目描述题意概括思路历程1.设计转移2.有没有发现少了个\(K\)代码实现题目描述Sheng_bill不仅有惊人的心算能力，还可以轻松地完成各种统计。在昨天的比赛中，你凭借优秀的程序与他打成了平局，这导致Sheng_bill极度的不满。于是他再次挑战你。这次你可

P1972[SDOI2009]HH的项链【解法一】树状数组解法本题核心：如何判断一个区间内的贝壳是否重复？当右端点\(r\)固定时，不论\(l\)取何值，对于任意一组重复的贝壳，都可以只统计最右端的贝壳。原因：设一组重复贝壳中最右端的贝壳所在的位置为\(pos_r\)，那么当\(pos_r<l\)时，其他

一道很妙的状压dp，差不过做过才会，数组设置的很妙也很难我们对T字符串进行考虑首先T字符串每一位只能是小写字母。所以我们可以先预处理T字符串每一位为某个小写字母

多次询问子序列[L,R]包含了多少种不同的数？  把问题离线，按照R排序ans[id]=qq(r)-qq(l-1)但前面重复的要减去，比如（1，2，1，1）#include<bits/stdc++.h>usingnamespace

题目传送门题意分析题目部分本题核心：如何判断一个区间内的贝壳是否重复？当右端点\(r\)固定时，不论\(l\)取何值，对于任意一组重复的贝壳，都可以只统计最右端的贝壳。原

P1972 [SDOI2009]HH的项链将全部输入排序，进行离散化#include<bits/stdc++.h>usingnamespacestd;#definerintregisterintconstintN=1e6+7;inta[N],tr

P1972SDOI2009HH的项链-洛谷|计算机科学教育新生态(luogu.com.cn)维护一个长度同为\(n\)的数组\(b\)。一个指针\(R\)从\(1\)扫到\(n\)并做如下操作：检查

首先考虑分别求出在两个人最短路上的边，这个就是用\(s\)跑一遍最短路，\(t\)跑一遍最短路，然后枚举边\((u,v)\)，如果满足\((s\tou)+(u\tov)+(t\tov)=(s\tot)\)那么

题意传送门\(N\timesM\)的矩形，格点是共\(W\)棵常青树或墓地。对于一块墓地，它的虔诚度为让它正上下左右各恰有\(k\)棵常青树的方法数量。求出整个矩形公墓的虔诚度总