[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\)棵常青树的方法数量。求出整个矩形公墓的虔诚度总