2019 xdu网络赛F XDOJ 1409: 背包弹夹平底锅
网络赛最难的一个题，也是我唯一一个不会做的。
看了大大的题解发现我其实已经推到了倒数第二步T_T
但是眼拙没看出来可以写成卷积形式。。。所以按照那个推法无论如何都是O(n^2)的复杂度，变成卷积形式就可以用fft加速直接O(nlogn)一次性求出所有点的值了。。。
继续阅读“[比赛补题][FFT][组合数学][母函数][×]2019 xdu网络赛F XDOJ 1409: 背包弹夹平底锅”
[组合数学][大组合数取模][TreeDp] UVA 1436 Counting heaps
思路比较简单但是很经典的一题，最近一直在补数学。。
用dp(u)表示以节点u为根的种类数，则由基本的组合数学可以得出\[dp(u)=(\frac{(n-1)!}{\prod size(v)})*\prod dp(v),\ u\ is\ v’s\ parent\] 其中\[size(v)\]是以v为根的子树的大小。然后由于这里模值是任取的，所以不能用求逆元的方式来做，否则的话也太简单了。
考虑进一步化简这个式子，把\[dp(v)\] 们展开（脑海中展开）可以发现对于每个节点来说，他以 \[(size(v)-1)!\]的形式出现在分子上一次，以\[size(v)!\]的形式出现在分母上一次，所以最终把所有节点（不仅仅是root的直接儿子）全部代进去就可以得到\[dp(root)=(\frac{(n-1)!}{\prod_{v=2}^{v=n} size(v)})\]
继续阅读“[组合数学][大组合数取模][TreeDp] UVA 1436 Counting heaps”
[组合数学][数论][矩阵][优化][Polya][状压DP][x] XDOJ 1296 敬老师的手环II
去年校赛的时候感觉此题难的一批，，，昨天做polya练习题的时候做到了poj 2888去翻了下matrix67大神的十个利用矩阵乘法解决的经典题目中的第9题才恍然大悟。。。Oooooor2 做完这俩题再来看XDOJ的这个题已经是自然而然就可以搞出结果的了。
这个题的思想就是：把每一列3*1的小方格当成一个“珠子”，把他可能的8种情况当成“颜色”，然后这些颜色同时也代表状态，类似于poj2888的颜色相邻限制，这里的状态之间“能不能相邻”其实就是在状压dp里“能不能转移”的限制，不同状态之间的转移图如下（来自matrix67的那篇文章
[数论][二次剩余应用][组合数][等比数列] ZOJ 3774 Power of Fibonacci
主要是利用了斐波那契数列对mod1e9+9时二次剩余的性质。说起来这个性质也是很奇葩，只见过两次应用这个题目的情况，一个是这个题一个是/cf.
二次剩余的定义是 当存在某个x使得x^2 \equiv d(mod p)成立时，称“d是模p的二次剩余”，当对任意不成立时，称“ d是模 p的二次非剩余”
而对于斐波那契数列有更具体的性质：
继续阅读“[数论][二次剩余应用][组合数][等比数列] ZOJ 3774 Power of Fibonacci”
[数学][计算几何][极角排序][递推] UVA 11529 Strange Tax Calculation
题目链接 https://cn.vjudge.net/problem/UVA-11529
（复习期末期间日常的小题
想到了考虑每个点被多少个三角形包围，但是没想到怎么算。。。主要还是计算几何太萎le，完全没有想到可以极角排序处理emmm。
具体的就是，考虑每一个点被多少个三角形包含，但是直接考虑也不好计算，可以考虑反向计算出不被多少个三角形包含，这个计算就要用到极角排序了。。。循环遍历每个点，在每个xi点，都对所有的其他点（姑且称为角点吧）相对于这个xi点的极角做一个排序，然后利用三角形的性质，选一个方向（顺时针或者逆时针都行），依次考虑“以每个角点为最小极角与之角度差小于pi的最大角度点之间有多少个点“，可能难以理解，画个图就好了，算出来点的数量p（p包含最大的那个点）之后C(p,2)就是“包含当前最小角点的所有的不覆盖xi点的三角形数量”，依次累加就好了。。。
另外，画个图就会发现，还需要考虑圆周转一圈的情况，所以要把排序后的极角数组复制一遍，而且复制出来的这个数组每个元素还要加2pi！（这个自己试试就知道了）
然后就是找最大点的步骤要小心，很容易写错。。莫名其妙，也可能是我最近复习微机原理复习傻了。 继续阅读“[数学][计算几何][极角排序][递推] UVA 11529 Strange Tax Calculation”
[二维DP][组合计数][利用对称性简化问题] UVALive 3295
https://vjudge.net/problem/UVALive-3295
这个题目和3720很像，尤其是在应用对称性的时候。这种题目有个很有趣的地方就是他每次都是对局部进行刻画然后得到了全局的信息，或者可以这么说，按照某一种策略使得某种属性所有的状态都被考虑进去。在这里就是计算一个共线的点的问题，按照和题目3720算法本身的推其实是只能算出来“斜率为正”的一类斜线，但是算的是“所有的斜率为正”的斜线，也就是覆盖了每一种情况，那么剩下的情况其实只有水平竖直和斜率为负的斜线，但是由对称性可知斜率为负的斜线一定和斜率为正的斜线数量相等，因此只需要*2即可，而我自己一开始一直在纠结的问题就是怎么算出来这些反向斜线，其实最后全局考虑只需要把算出来的正向斜线情况*2即可。最后的结果就是C(3,(m+1)*(n+1))-共线的三点数量。
wa的话有一个问题是，在gcd的算法中如果a和b有一个数字为0那么返回值就会是0，这种情况在这里的递推过程中是会出现问题的，需要注意让循环从2开始，也算是一个小小的坑吧。。以前没有注意到。
[组合数学][数论][思维][空间对称转化][充要条件] UVALive 3720 Highways
很有意思的一个组合数学题。
整个题的最核心的思想就是，两个线段共线的判断！只要有两个点就可以确定一条线段（直线），那么只要再多一个点就可以确定这个点是否在和当前的这条线段共线了！所以两种算法的思想都在于一个2
第一种方法：最纠结的问题还是在于，怎么去重。想到了枚举角度的方法却没有想到怎么去重，还是思维不行。第一种方法是每次枚举所有可能的矩形，然后计算对角线的数量，这个很好算也就是有多少个矩形，直接(n-i+1)*(m-j+1)就行了。但是我们考虑的时候首先只考虑gcd(i,j)==1的情况，这种情况一定说明这种对角线的角度第一次出现（因为我们从小到大枚举i和j），所以对答案贡献为正，还有一种情况是gcd(i,j)==2，这说明之前已经出现过了这种对角线，所以这里要减去对应的数量，注意这里是最重要的：减去的是对应的数量，然后其他的gcd值不用+也不用-。原因就在于，如果你有一个4*4的或者3*3的矩形对角线重算了，那么在清除gcd为2的那一步当中其实就已经清除了所有的重复对角线！因为这个2会按照不同的起始点一直推下去。 继续阅读“[组合数学][数论][思维][空间对称转化][充要条件] UVALive 3720 Highways”
[数位DP][组合数学][整数分段] UVa 11038 How Many O’s?
自己写了个有点繁杂的数位dp，本来一发过还有点高兴，但是看了前排dalao代码发现自己写的太复杂了。。。。这个题其实只用组合数学就可以解emmmm
先上自己的屌丝做法：分段dp，从前往后，组合数学算下可以知道能预处理出来一段长度为n的可以包含前导0的数据的所有0的个数，我本来想的是用f(p,m,isf)表示当前是第p个数字，最大为m然后是否为上限isf表示状态，但是写着写着发现不用这么来。。。。所以其实到最后程序里的isf就没有用（在发现这一点的时候我就该想到其实不用这么“dp“），把当前位为0特判一下加上后面的所有可能数字（这个也可以预处理），算完当前这一位之后往下一位继续算。。。最后由于我在f里面的枚举都是从0开始，所以等于说算出来的是”可以包含前导0的数的0的个数“，所以在cal里面还要减去所有的前导0的个数。。。麻烦一批
再说dalao们的做法：其实这个前导0的问题很容易解决。。。从后往前算就ok了，每次算到一位的时候判断是不是0，不是0的话，可以想到当前位为0的话总共出现的次数是容易计算的：把整个数字从这个点分开成左右两段（不包括当前这一位），那么左边的数字*10^(右边的位数),如果当前为0那就不能这么算了（跟数位dp一个道理，isf的时候不能当成所有的情况来做）,但是仍然很简单：只要左边不是最大的那个数字，右边仍然可以取到所以情况，所以这时候把左边-1乘上右边的10幂，再加上右边所有的本身的上限就行了。。。还是看代码比较好说。