shyyhs

分类

DP专题(52) 图论(4) 多校补题(2) 数据结构(27) 数论(4) 日记(14) 未归档(38) 题解(330)

/ 注册

TA的专栏 440篇文章 0人订阅

415篇文章 3900人学习

AtCoder思维大提升

6篇文章 764人学习

kuangbin专题记录

0篇文章 0人学习

牛客每日一题推介(裙子计划~)

19篇文章 843人学习

全部文章（共469篇）

D. ConstructOR

比较奇怪的数学题叭... 要求一个xxx使之和a,ba,ba,b或后都能整除ddd. 首先a,ba,ba,b中minsufzeromin_{sufzero}minsufzero假如少于ddd的minsufzeromin_{sufzero}minsufzero这种一定是不存在酱紫的xxx的. 不妨...

数学

2022-11-15

0 515

G - Count Sequences

考虑差分. b1=a1,bi=ai−ai−1,bn+1=m−anb_1=a_1,b_i=a_i-a_{i-1},b_{n+1}=m-a_nb1=a1,bi=ai−ai−1,bn+1=m−an. 对于bib_ibi%333来说. 显然除了第111项和第n+1n+1n+1项可以是任意模3...

组合数学差分

2022-11-11

0 569

《人间油物》

在利用卷积使得各项相乘的时候,由于顺序会被交换,所以b数组要倒序输入,可以看成是两个卷积之间的配对. 画个图就懂了~ code: #include <bits/stdc++.h> using namespace std; typedef long long ll; const int...

fft

2022-09-01

0 730

多重集下的组合数

与多重集的排列数不同组合数即是不含有相同数交换的数. 并不是很难. Devu and Flowers 题面翻译 Devu 有 nnn 个花瓶，第 iii 个花瓶里有 fif_ifi 朵花。他现在要选择 sss 朵花。你需要求出有多少种方案。两种方案不同当且仅当两种方案中至少有一个花瓶选择花的数量...

容斥

2022-09-01

0 653

G - Yet Another RGB Sequence

数学不好的记录一下. 题目是给定R,G,BR,G,BR,G,B的数量.然后给你一个kkk,要求字符串中有kkk个RGRGRG的方案数. 考虑先放G,B,RGG,B,RGG,B,RG,最后补RRR. 考虑先放的方案数就是(numG+numB)!/(numG−k)!∗(numB)!∗(k)!(num_G...

2022-08-31

0 748

B - Adjacent Chmax

第一次自己写出700700700分的题!!! 记录一下. 首先能到iii位置后面的一定是满足iii后面的连续的maxmaxmax.这点很显然. 那么我们设置dpdpdp状态: fi,jf_{i,j}fi,j为到了第iii个位置,值是jjj的方案数.注意这是从111开始数到iii考虑本质不同的序列....

单调栈 dp

2022-08-16

1 741

FFT

推介这篇博客吧,写的真的挺好的. 算了说点自己的理解吧... 首先fftfftfft是解决两个多项式相乘把时间复杂度从O(N2)O(N^2)O(N2)优化到O(N∗logN)O(N*logN)O(N∗logN).学它可以解决一些用前缀不能解决的优化. fftfftfft里面引进了复数,它是非常的妙的...

fft

2022-08-12

0 718

1426

大概这才是期望dpdpdp的入门题吧. 可以合并当前项的dpdpdp哦！首先定义方程fif_ifi表示已经拿到了iii个,还需要拿多少次能全部拿完的期望. 那么容易得到转移方程: fi=fi∗(i/n)+fi+1∗(1−i/n)+1f_i=f_i*(i/n)+f_{i+1}*(1-i/n)+1f...

期望dp

2022-08-10

0 507

斜率优化dp

是一种可以针对i j具有某种单调性来用斜率优化dp{dp}dp转移的一种方式. 例:BZOJ1010 玩具装箱toy 很容易的写出dpdpdp方程,令fif_ifi表示解决前iii个的最小花费. 那么转移也很明显就是:fi=fj+(sumi−sumj−L+i−j−1)2f_i=f_j+(sum_i...

斜率优化dp

2022-08-09

0 511

干草堆tower

一个很好的dp. 显然最优的方案一定是最瘦的情况,从前往后是没有转移性质的,也不符合dp的最优解转移. 那么考虑从后往前转移,定义: fif_ifi表示到了第iii个的{最小宽度是多少,高度是多少},因为到了iii最小宽度的情况下,高度是最高的,顺带记录下高度即可. 转移很显然： fi.first...

单调队列优化dp

2022-08-07

0 477