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篇）

BZOJ 3930 [CQOI2015]选数-数论+递推

传送门题意：从区间[L,H]（L和H为整数）中选取N个整数，求N个整数最大公约数刚好为K的选取方案有多少个，答案模1e9+7 1≤N,K≤10^9，1≤L≤H≤10^9，H-L≤10^5 Solution：并不是非常理解莫反怎么做= = 注意到H-L≤10^5 尝试在这上面做文章...

2021-08-18

0 415

AtCoder Regular Contest 089 E-GraphXY-构造题

题意：给一个n,m的矩阵dx,y,构造一张小于300个点的有向图，边上的权值范围为[0,100]，也可以是未知整数x或y，要求给出固定的S，T，当x分别取[1,n]，y分别取[1,m]时，S到T的最短路为 dx,y 1≤n,m≤10 1≤dx,y≤100(1≤x≤n,1≤y≤m) ...

2021-08-18

0 302

Codeforces 839D Winter is here-容斥

传送门题意：给出一个n个数的数列 ai a i ,考虑其中所有gcd大于1的集合，每个集合的贡献是gcd乘上集合的大小，求这个数列的总贡献%1e9+7 (1 ≤ n ≤ 200000,1 ≤ ai ≤ 1000000) ( 1 ≤ n ≤ 200000 , 1 ...

2021-08-18

0 421

BZOJ2194: 快速傅立叶之二-FFT

题意：给出a,b,计算 C[k]=∑n−1i=ka[i]∗b[i−k] C [ k ] = ∑ i = k n − 1 a [ i ] ∗ b [ i − k ] , n<=1e5 n <= 1 e 5 Solution: 回想多项式乘法： ∑2n−2k=0(∑k=i+ja...

2021-08-18

0 352

bzoj3527:[Zjoi2014]力-FFT

传送门题意：给出n个数 qi q i ,F和E的定义如下： Fj=∑i<jqiqj(i−j)2−∑i>jqiqj(i−j)2 F j = ∑ i < j q i q j ( i − j ) 2 − ∑ i > j q i q j ( i − j ) 2 ...

2021-08-18

0 527

bzoj2951: [Poi2001]Goldmine-线段树

题意：给出n个天然金矿石的位置，选一小块长方形的矿地，此矿地长和宽为s和w且平行于坐标系统的轴线。这块地的价值是这块区域内天然金矿石的数量。计算出这块地的最大可能价值。（ 1≤s,w≤10000,1≤n≤15000 1 ≤ s , w ≤ 10000 , 1 ≤ n ≤ 15000 ） ...

2021-08-18

0 335

Codeforces 906D:Power Tower-扩展欧拉定理

传送门 ##题意：给你n个数w和一个数p，q个询问，每次询问一个区间[l,r],求 w l ( w l + 1 ( w l + 2 . . . w r ) ) m o d p w_l^{(w_{l+1}^{(w_{l+2}...^{w_r})})}\mod p wl(wl+1(wl+2....

2021-08-18

0 459

Codeforces 920F SUM and REPLACE-线段树+欧拉筛

传送门题意： n个数a，q个操作，两种操作类型： 1.[l,r]区间中每个数替换为这个数的因数个数 2.区间求和 q,n<=3e5,ai<=1e6 q , n <= 3 e 5 , a i <= 1 e 6 Solution: 值为1或2的数是不需要再进...

2021-08-18

0 412

Codeforces 126B Password- z-box算法

传送门题意：给出一个字符串，求不等于前后缀的最长的一段子串，使得这段子串即是前缀也是后缀 Solution: 这道题如果使用KMP解决并不这么直观使用z算法可以轻松地解决（如果没有学过z算法请点击这里）处理出z数组后，我们记录前i项的z的最大值对于第i+1项，如果z[i+1]...

2021-08-18

0 560

Codeforces 535D Tavas and Malekas-字符串匹配

传送门题意：给出文本串的长度n，给出模式串以及模式串在文本串中出现的位置，求有多少种文本串满足条件。 Solution: 在文本串中暴力加入模式串，最后判断匹配位置是否和给出的相符即可。代码（z-box赛高！）： #include<cstdio> #include<...

2021-08-18

0 520