题意 给定一个正整数 www 及 www 个数 c0,c1,⋯ ,cw−1c_0, c_1, \cdots,c_{w - 1}c0​,c1​,⋯,cw−1​ qqq 组询问，每次询问给定一个正整数 nnn，计算有多少个长度为 nnn 的字符串满足： 每个字符只能取数字 0∼w−10 \sim w - 10∼w−1 数字 iii 至少出现 cic_ici​ 次 对 998 244 353998 \, 244 \, 353998244353 取模。 2≤w≤10,1≤ci≤5×104,∑i=0w−1ci≤5×1042 \le w \le 10, 1 \le c_i \le 5 \times 1...

1. 最 大 独 立 集 \large1.最大独立集 1.最大独立集 选出最多的点,使得所有点都是不相邻的 状态表示： d p i , j dp_{i,j} dpi,j​ 表示以 i i i 为根的树，如果 j j j 为 0 0 0 ，表示不选这个点，如果 j j j 为 1 1 1，表示选这个点 属性： Max \text{Max} Max 状态计算： 如果当前点 i i i 不选，那么子节点 j j j 可以被选或不被选： d p i , 0 = ∑ k = 1 n max ⁡ ( d p j k , 0 , d p j k , 1 ) dp_{i,0}=...

题面: 已 知 函 数 f ( x ) = x ( 1 − ln ⁡ x ) 已知函数f(x)=x(1-\ln{x}) 已知函数f(x)=x(1−lnx) ( 1 ) 讨 论 f ( x ) 的 单 调 性 (1)讨论f(x)的单调性 (1)讨论f(x)的单调性 ( 2 ) 设 a , b > 0 , a ≠ b , 且 b ln ⁡ a − a ln ⁡ b = a − b , 证 明 : 2 < 1 a + 1 b < e (2)设a,b>0,a\ne b,且b\ln{a}-a\ln{b}=a-b,证明:2<\frac{1}{a}+\frac{1}...

1. 已 知 函 数 f ( x ) 连 续 且 f ( x + 2 ) − f ( x ) = cos ⁡ x , ∫ 0 2 f ( x ) d x = 1 , 求 ∫ − 1 1 f ( x ) d x 1. 已知函数f(x)连续且f(x+2)-f(x)=\cos x,\int^{2}_{0}f(x)dx=1,求\int^{1}_{-1}f(x)dx 1.已知函数f(x)连续且f(x+2)−f(x)=cosx,∫02​f(x)dx=1,求∫−11​f(x)dx 分析： 构造。题目中给出了两点差的函数式，想到构造变动上下限积分，题眼 ∫ 0 2 f ( x ) d x = 1 \int^...

由于算法提高课的数位DP的非搜索做法比较难想，所以总结一下数位 DP \text{DP} DP的 DFS \text{DFS} DFS写法，个人感觉 DFS \text{DFS} DFS做法才是数位 DP \text{DP} DP的正解。 数位DP问题一般给定一个区间 [ L , R ] [L,R] [L,R]，问区间满足的条件的数有多少个。 可以利用前缀和来求解答案： ∑ i = 1 R a n s i − ∑ i = 1 L − 1 a n s i \sum_{i=1}^{R} ans_i - \sum_{i=1}^{L - 1} ans_i ∑i=1R​ansi​−∑i=1L−1​a...

最近公共祖先 (LCA) \text{(LCA)} (LCA)： 给定一颗有根树，若节点 z z z既是节点 x x x的祖先，也是节点 y y y的祖先，则称 z z z是 x , y x,y x,y的公共祖先。在 x , y x,y x,y的所有公共祖先种，深度最大的一个称为最近公共祖先，记作 LCA ( x , y ) \text{LCA}(x,y) LCA(x,y) 做法一：向上标记法 从 x x x向上走到根节点，标记所有经过的节点，再从 y y y向上走，当第一次遇到已标记的节点是，那么此节点就是 LCA ( x , y ) \text{LCA}(x,y) LCA(x,y) ...

在介绍算法之前先引入几个概念： 时间戳： 在深度优先搜索时，每个点 x x x第一次被访问的顺序为时间戳，记作 d f n [ x ] dfn[x] dfn[x]（从 1 1 1开始） 追溯值： 从 x x x开始走，所能遍历到的最小时间戳，记作 l o w [ x ] low[x] low[x] 1. tarjan 1.\text {tarjan} 1.tarjan求 SCC \text{SCC} SCC 给定一张有向图 G G G， ∀ u , v \forall u,v ∀u,v，即存在从 u u u到 v v v的路径又存在从 v v v到 u u u的路径，那么该图 G G...

树状数组的基本应用： O ( log ⁡ n ) O(\log n) O(logn)单点修改、区间查询 原理： 设区间 [ 1 , R ] [1,R] [1,R]，对区间右端点 R R R做二进制拆分，有： R = 2 x 1 + 2 x 2 + ⋯ + 2 x k R=2^{x_1}+2^{x_2}+\cdots+2^{x_k} R=2x1​+2x2​+⋯+2xk​ 假设 x 1 ∼ x k x_1\sim x_k x1​∼xk​严格单调递减，那么可以把区间 [ 1 , R ] [1,R] [1,R]拆分成 log ⁡ R \log R logR个区间 [ 1 , 2 x ...

线段树是用于维护区间信息的一种数据结构，可以在 O ( log ⁡ n ) O(\log n) O(logn)的复杂度内实现区间修改，区间查询等操作，还可以维护各种满足结合律的信息。 原理： 线段树的建树：设有数组 a i , i ∈ [ 1 , n ] a_i,i \in[1,n] ai​,i∈[1,n]，把一整个数组区间划分为两个子区间，设区间 [ l , r ] [l,r] [l,r]，那么取区间中点 m i d = ⌊ l + r 2 ⌋ mid=\left \lfloor \frac{l+r}{2} \right \rfloor mid=⌊2l+r​⌋，那么区间就会被划分为 [ ...

前置知识1:整除分块 ① : ⌊ a b c ⌋ = ⌊ ⌊ a b ⌋ c ⌋ ①:\lfloor \dfrac{a}{bc} \rfloor = \lfloor \dfrac{\lfloor \dfrac{a}{b} \rfloor}{c} \rfloor ①:⌊bca​⌋=⌊c⌊ba​⌋​⌋ 证明： a b = ⌊ a b ⌋ + r , r ∈ [ 0 , 1 ) \dfrac{a}{b}=\lfloor \dfrac{a}{b}\rfloor + r,r\in[0,1) ba​=⌊ba​⌋+r,r∈[0,1) ⌊ a b c ⌋ = ⌊ a b ⋅ 1 c ⌋ \lfl...

题意： 求 ∑ i = a b ∑ j = c d [ gcd ⁡ ( i , j ) = k ] \sum_{i=a}^{b}\sum_{j=c}^{d}[\gcd(i,j)=k] i=a∑b​j=c∑d​[gcd(i,j)=k] 分析： 用二维前缀和的思想，把答案分为 4 4 4个部分 令 S ( x , y ) = ∑ i = 1 x ∑ j = 1 y [ gcd ⁡ ( i , j ) = k ] 令S(x,y)=\sum_{i=1}^{x}\sum_{j=1}^{y}[\gcd(i,j)=k] 令S(x,y)=i=1∑x​j=1∑y​[gcd(i,j)=k] 则 ...

题意： 设 d ( x ) d(x) d(x) 为 x x x 的约数个数，求 ∑ i = 1 N ∑ j = 1 M d ( i j ) \sum_{i=1}^{N}\sum_{j=1}^{M} d(ij) i=1∑N​j=1∑M​d(ij) 分析： 首先 i = p 1 α 1 ⋯ p k α k , j = p 1 β 1 ⋯ p k β k , i × j = p 1 α 1 + β 1 ⋯ p k α k + β k i=p_1 ^{\alpha_1}\cdots p_k^{\alpha_k},j=p_1 ^{\beta_1}\cdots p_k^{\beta_k},...

BSGS (Baby Step Giant Step) : \text{BSGS (Baby Step Giant Step)}: BSGS (Baby Step Giant Step): 给定正整数 a , b , p , a ⊥ p a,b,p,a \perp p a,b,p,a⊥p ，求满足 a x ≡ b (  mod  p ) a^{x} \equiv b(\text{ mod } p) ax≡b( mod p) 的最小非负整数 x x x 首先由欧拉定理的推论有： a x ≡ a x  mod  φ ( p ) (  mod  p ) a^x\equiv a^{x...

题意： 求 2 ∗ ∑ i = 1 n ∑ j = 1 m gcd ⁡ ( i , j ) − n ∗ m 2*\sum_{i=1}^{n}\sum_{j=1}^{m}\gcd(i,j)-n*m 2∗i=1∑n​j=1∑m​gcd(i,j)−n∗m 分析： 莫比乌斯反演： 那么只需要求 ∑ i = 1 n ∑ j = 1 m gcd ⁡ ( i , j ) \sum_{i=1}^{n}\sum_{j=1}^{m}\gcd(i,j) i=1∑n​j=1∑m​gcd(i,j) 枚举每个 gcd ⁡ ( i , j ) \gcd(i,j) gcd(i,j) 的值 ∑ d = ...