thchuan2001的博客

原创 题解Atcoder Grand Contest C - Squared Graph

Problem Statement Takahashi has received an undirected graph with N vertices, numbered 1, 2, ..., N. The edges in this graph are represented by (ui,vi). There are no self-loops and multiple edges in th

原创 （带讲解）bzoj 4830 抛硬币 组合式推导+拓展lucas

卡常！！！题意:有两个人，第一个人要扔a次硬币，第二个人扔b次硬币（a>b)，如果第一个人的正面朝上比b多则a获胜，求a获胜的话有多少种方案。要求a-b的范围是1e5，但是a和b都很大，所以复杂度要和a-b有关。首先可以列出组合数公式 ∑i=1a∑j=0i−1(ai)(bj)\sum_{i=1}^a\sum_{j=0}^{i-1}\begin{pmatrix}a\\i\end{pmatrix}\b

原创 （带讲解）poj2409&poj1286 polya模板

题意：用m种颜色染长度为n的环，旋转和对称认为是同一种方案，求本质不同的方案数。我们只要考虑出置换群G，直接套polya公式即可。首先，考虑一下旋转。对于旋转，所有的节点都会旋转，所以循环节长度应该是一样的，这个长度是多长呢？设每次转x格，现在在p号点，走k次后回到p点，即p+kx\equiv p (\%n)kx\equiv 0 (\%n)所以kx模n等于0，即kx是n的倍数。当然kx还是x的倍数，

原创 群论&polya定理笔记

一、群（一）定义一种包含一些元素和相关元素的一个运算符的结构（二）基本性质1、封闭性：∀x,y∈S,x⊕y∈S(x,y可以相等) 2、结合律：∀a,b,c∈S,a⊕b⊕c=a⊕(b⊕c)(a,b,c可以相等) 3、单位元：∃e∈S,∀x∈S,e⊕x=x⊕e=x(x,e可以相等，我们往往用e代表单位元，也叫幺元) 4、逆元：∀x∈S,∃y∈S,x⊕y=y⊕x=e(x,y可以相等，我们称y为x的逆元，记

原创 （带讲解）bzoj2738 整体二分

一般来说，整体二分是有模板的题意：给出n*n的矩阵，求出子矩阵的k小值。方法1：二维主席树，把询问分成4个，线段树加加减减然后查询即可方法2(正解):整体二分大体思路:二分一个答案mid，然后把所有小于等于mid的数使用二维树状数组维护，然后判断询问集合中子矩阵中元素个数是否小于等于k，如果是，则mid也许可以更小，否则，mid只能变大。二分细节：依旧按照普通二分的思路，在每次元素个数>=k是记录这

原创 bzoj3223: Tyvj 1729 文艺平衡树 平衡树上的区间翻转标记

题意：给出初始序列a[n]=n进行m次翻转，求最终序列。只有在一开始，第几个点就是几号店。。。在进行翻转后，如果还要翻转l-r，不是对l节点和r节点进行操作，而是对第l个和第r个点进行翻转。首先，如果我们对整个序列建立平衡树，因为没有节点的增加和减少，所以整个数的结构建好了就不会改变。 即SBT的大小关系是下标，而不是值。这样，就有了n个节点的线段树。我们考虑怎么进行翻转，如果对整个序列进行翻转，只

原创 （带讲解）bzoj1030 AC自动机+dp

第一道AC自动机上的dp题意是给出一些字符串，求长为m的字符串包含这些的一共有多少个，字符集A-Z首先运用补集转换，转而求不含这些串的个数，最后用26^M减掉就行根据输入的字符串建立AC自动机dp[i][j]表示当前考虑了i位，当前停留在AC自动机的j号节点每一次可以由dp[i][j]转移到dp[i+1][k]，k是枚举第i+1为后作为j的儿子在AC自动机上的编号枚举k，就是第i+1为填什么，然后进

原创 图片链接，没什么用\(^o^)/