Fizzmy

分类

--------DP--------(1) CDQ分治(1) DP(11) FFT(4) z-box(6) 主席树(1) 二分(2) 分数规划(1) 分治(1) 区间DP(3) 博弈论(2) 后缀数组(2) 哈希(1) 学习笔记(2) 容斥(1) 并查集(4) 强连通分量(1) 扫描线(1) 数位DP(3) 数论(12) 斯特林数(1) 暴力(2) 最小生成树(1) 最短路(1) 期望DP(4) 未归档(5) 树形dp(4) 模拟(1) 模板(3) 游记(1) 状态压缩(8) 线段树(12) 组合数学(1) 网络流(4) 脑洞(8) 莫比乌斯反演(2) 贡献法(3) 题解(2)

/ 注册

全部文章（共123篇）

BZOJ3884 上帝与集合的正确用法-扩展欧拉定理

传送门题意：求 2(2(2...))modp 的值，多组询问。 p≤107 。 Solution: 根据扩展欧拉定理，我们知道：当 b≥φ(p) 时， ab≡ab%φ(p)+φ(p)modp 此公式的具体证明可以百度扩展欧拉定理我们假设 f(p)=2(2(2...))modp ,...

2021-08-18

0 545

BZOJ2154+BZOJ2693 Crash的数字表格&jzptab-莫比乌斯反演

传送门 BZOJ2154 题意：求 ∑ni=1∑mj=1lcm(i,j) ∑ i = 1 n ∑ j = 1 m l c m ( i , j ) Solution: 看到此题首先想到这步： ∑i=1n∑j=1nlcm(i,j)=∑i=1n∑j=1nijgcd(i,j) ...

2021-08-18

0 372

BZOJ2987-earthquake

权限题。题意：给定a,b,c,求满足方程 Ax+By<=C 的非负整数解 A,B<=109,C<=min(A,B)∗109 Solution: 类欧几里得算法模板题没学过的点击这里变形一下这个式子： y<=C−AxB 但是这个式子如果直接套用...

2021-08-18

0 415

BZOJ2957 楼房重建-线段树

题意：小A的楼房外有一大片施工工地，工地上有N栋待建的楼房。每天，这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆，数自己能够看到多少栋房子。为了简化问题，我们考虑这些事件发生在一个二维平面上。小A在平面上(0,0)点的位置，第i栋楼房可以用一条连接(i,0)和(i,Hi)的线段...

2021-08-18

0 386

Codeforces 380E - Sereja and Dividing-贡献法

改编题意：有n杯水排成一行，第i杯水中有 wi 单位体积的水. 他会选择一个区间 [l,r] ，并拿一个初始为空的杯子（杯子的容积无限大），他可以重复无限次以下操作： • 选定任意一杯水i， i∈[l,r] ． • 使i和它拿着的杯子里的水的体积变为它们的平均值．小C希望进行若干操作...

2021-08-18

0 314

BZOJ 4596 黑暗前的幻想乡-矩阵树定理+容斥原理

传送门题意：幽香要修建幻想乡的公路。幻想乡有 N 个城市，之间原来没有任何路。幽香向选民承诺要减税，所以她打算只修 N- 1 条路将这些城市连接起来。但是幻想乡有正好 N- 1 个建筑公司，她打算让每个建筑公司都负责一条路来修。每个建筑公司都告诉了幽香自己有能力负责修建的路是哪些城市之间...

2021-08-18

0 510

Codeforces 343D Water Tree-线段树

传送门题意：给你一棵树，有三种操作： 1. 给一个点及其子孙赋值为1 2. 给一个点及其祖先赋值为0 3. 求一个点是1还是0 Solution：这道题显然可以用树剖做，但是复杂度不优秀（两个log），这里说一种一个log的做法：先跑出树的dfs序，对dfs序建一棵线段树，那...

2021-08-18

0 376

bzoj3134 [Baltic2013]numbers-数位dp

题意：一个数是非回文数当且仅当不包含长度大于1的回文数。比如16276是无回文数，而17276因为含有727而不是。求区间内有多少个非回文数。 Solution：非常经典的数位dp问题，一开始想到f[len][pre][pre2][0/1]表示第len位，第len-1位是pre，第le...

2021-08-18

0 297

BZOJ2142 礼物-扩展lucas

传送门题意：给定n及m个数a[1…m],再给定一个模数P，求 ∑ni=1Cain−∑i−1j=1aj%P ( 1≤n≤109,1≤m≤5 ,设 P=pc11∗pc22∗pc33∗…∗pctt ， pi 为质数, 1≤pcii≤105 ) Solution: 扩展lucas定理模板...

2021-08-18

0 358

HDU5693 D Game-区间dp

vjudge传送门题意：有一个公差集合{D}，有n个数字每次执行以下操作： 1. 在当前剩下的有序数组中选择x(x≥2)个连续数字； 2. 检查1选择的x个数字是否构成等差数列，且公差 d∈{D} ; 3. 如果2满足，可以在数组中删除这x个数字； 4. 重复 1−3 步，直到无...

2021-08-18

0 565