shyyhs

分类

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

/ 注册

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

415篇文章 3897人学习

AtCoder思维大提升

6篇文章 750人学习

kuangbin专题记录

0篇文章 0人学习

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

19篇文章 840人学习

全部文章（共6篇）

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 557

魔改森林来自专栏

前言: 很久很久以前就看到这个题目.记得这题应该是小乔出的.当时我队友来问我,我跟他讲了一下35分的做法.因为那个时候太菜了,不会容斥原理. 思路: 这题前面1000个数据直接dp即可.后面1e5,直接组合数预处理+容斥原理即可. 代码: #include <bits/stdc++.h>...

容斥原理 dp 组合数学

2021-01-27

3 829

Paint Box 来自专栏

一直不是很懂容斥原理的原因,学二分图的时候再看看!我们很容易知道,求给n个位子上色,可以最多使用k种颜色的方案数是.由容斥原理想到可以把最多->等于.那么就是最多使用k种颜色-最多使用k-1种颜色+最多使用k-2种颜***r>那么直接这样做就好了.(值得注意的是:因为取模了,所以会存在负...

容斥原理组合数学

2021-01-21

1 692

二分图染色

邓老师题解写的十分的好.首先把完全二分图转化成一个二维的棋盘,因为完全二分图的连边可以把左边看成横坐标和右边看成纵坐标.如此题目就变成了,棋盘中同一横纵坐标不能存在相同颜色,且绿色根本不影响结果,我们不妨假设棋盘原本都是绿色,然后涂上红蓝两色...orz我们不妨设f[n]是一种颜色满足要求的所有涂法...

数学 DP 组合数学

2020-08-21

2 795

随风飘来自专栏

是一个组合数学问题,朴素的对于每个都不取k,那就是两个for的事.但是对于取k,我们应该如何分析呢?总的是n,我们拿走k个.在拿走的过程中,我们考虑始终保留两个特殊的,假设说我不存在取的过程,那么这两个产生的贡献必定是一次lcp.但是我们考虑拿走,这个它会多几次呢?其实也挺显然的,C(n-2,k)考...

组合数学

2020-08-01

4 857

错排&排列计数题解来自专栏

不要我为啥更这题,因为这种题,代码简单,思路简单.dp:先讲讲错排公式,D[1]=0,D[2]=1.这个是初始值.下面讲讲转移方程:D[i]=(n-1)*(D[i-1]+D[i-2]).考虑把第n个元素放到任意一个地方,那就有n-1种放法,假定我放的位子为k,那么我k就有两种放法,第一种是放到n的位...

dp 组合数学

2020-07-10

2 666