题意给一个数字串$s$和正整数$d$, 统计$s$有多少种不同的排列能被$d$整除数据范围：$s$的长度$\le 10,1 \le d \le 1000$题解直接计算整除的较为麻烦，可以状压使用过的数$d$并记录当前数模$d$的余数，再来表示方案数用$f[i][j]$表示选用过的数状态压缩为$i$，当前余数为$j$易得状态转移方程$$f[i|(1<<j)][(k*10+a[j])...

题意给出一个数列，有$m$次询问，求$[l,r]$之间有多少个出现次数$\ge 2$的数数据范围：$1 \le n,m \le 2 \cdot 10^6$题解对于每个区间，若一个数出现了$\ge 2$次，将其贡献计在第$2$个上（因为第$1$个无法产生贡献，而$\ge 2$与$=2$产生的贡献并无区别）这样，记录一个$nxt[i]$表示下一个与$i$相等的数出现的位置将询问离线，按左端点排序...

题意给出一个连成树的有向图，求拓扑序数量数据范围：$1 \le n \le 1000$题解树形$dp$，用$f[i][j]$表示以$i$为根的子树中，节点$i$的排名为$j$的方案数考虑转移，对于$u$为$v$的父节点，$x$在原序列中排名为$p_1$，新序列中排名为$p_3$；$y$在原序列中排名为$p_2$，新序列中排名为$p_4$，从$f[u][p_1]$与$f[v][p_2]$转移到...

题意一个$n \times m$的方格，初始时每个格子有一个整数权值接下来每次有$2$种操作改变一个格子的权值求一个子矩阵中某种特定权值出现的个数数据范围：$n,m \le 300,1 \le c \le 100$题解$n,m,c$较小，对于每个$c$开一个二维树状数组维护代码：#include<iostream> #include<cstdio> using nam...

题意求长度$\le$最短路$+k$的路径数数据范围：$n \le 100000,m \le 200000$题解首先需要跑一边最短路找到这个最短路；虽然保证存在$1 \rightarrow n$的路径，但并不是所有的点都能到$n$，所以应跑反向图用$f[u][i]$表示从$u$到$n$的路径中$\le dis[u][n]+i$的路径数，则答案为$f[1][k]$对于转移，考虑一条边$u \ri...

题意略数据范围：$1 \le n \le 100$题解数据范围较小，可直接$dfs$越过连续$1$为int nx=x+v[i][0],ny=y+v[i][1],cnt=1; for(;nx>=1 && nx<=n && ny>=1 && ny<=n && a[nx][ny];nx+=v[i][0],ny+...

题意对于一个数列，有$2$种操作：$1 \ x$ 询问$\ge x$的连续段的个数$2 \ i \ x$ 将$a_i$的值修改为$x$数据范围：$1 \le n,m \le 200000,1 \le a_i,x \le 10^9$题解首先对于一个询问考虑：将$\ge x$的数定义为$1$，$< x$的数定义为$0$；那么一个段的构成应为$$011 \dots 110$$即一个$01$+...