ACM--组合数学
关注
分享
扫一扫
animalcoder
NULL
展开
-
Codeforces 1278F Cards 二项分布的期望 第二类斯特林降幂
题意：给定n,m,k对二项分布 x~B(n,1/m)，求 E(x^k)n,m<998244353,k<=5005首先：E(x^k)!=(E(x))^k思路：由期望公式得：由第二类斯特林降幂得：（将i^k拆开，S(k,j)为第二类斯特林数）交换求和顺序：化简：( j>k时S(k,j)=0 所以枚举到min(n,k)，然后后面将组合数拆开)...原创 2019-12-31 16:41:08 · 339 阅读 · 0 评论 -
BZOJ3505 组合数学+整点计数
37 BZOJ3505 gcd+组合数学题意：n*m的网格有多少个网格三角形 n,m<=1000思路：总体减去三点共线的数目三点共线：水平，垂直都好算，打斜的怎么算？（不一定是对角线！！）这样：枚举n,m作线段(0,n),(m,0)中间有gcd(m,n)-1个点可以选，这条线有(n+1-i)*(m+1-j)种平移方案（向上向右）//n*m的网格里有多少个三角...原创 2018-09-07 23:49:53 · 215 阅读 · 0 评论 -
BZOJ1853 容斥DFS+剪枝
36.BZOJ1853容斥DFS+剪枝题意：问l,r内有多少个数满足：是 只有6或8组成的数 的倍数 l,r<=1e10比如12,48,6,68均满足要求//BZOJ1853 题意：问l,r内有多少个数满足：是 只有6或8组成的数 的倍数 l,r<=1e10 //思路：先预处理出 1e10内只有6 8组成的数（大概2500个）//然后2500内筛掉一些数是别的数的倍...原创 2018-09-07 23:53:36 · 200 阅读 · 0 评论 -
BZOJ3198 容斥+hash+恰好
35.BZOJ3198 容斥定理+哈希+恰好 题意：n个城市，每个城市有6个属性，求恰好有K个属性相同的城市有多少对？n<=1e5，0<=k<=6思路：恰好为K转化为至少为K，跟34一样，容斥系数是C（i,k）暴力枚举2^K,对每个状态 看有多少对，挂链哈希，自然溢出取模比如状态为15(001111)，哈希判断后4个属性有多少对相同的代码是转的，...转载 2018-09-07 23:59:37 · 162 阅读 · 0 评论 -
CF285E 容斥+恰好+DP
34.CF285E 容斥定理+DP+恰好 O(n^2)跟33类似（DP部分不会做，copy别人的题解，这道题的恰好K套路要学会= =）题意：1~n排列pi,若|pi-i|=1则i为好位置,求恰好K和好位置的方案数n,k<=1000思路：设Dp[i][j][2][2]为前i位有j个好位置，i是否使用，i+1是否使用恰好为K转化成至少为K来做(跟33一样)，ans=至少K...转载 2018-09-08 00:03:42 · 696 阅读 · 0 评论 -
BZOJ3622 容斥+DP+恰好
33.BZOJ3622 容斥定理+DP+恰好题意：各有n个数an,bn，上下11匹配，问恰好ai>bi 比ai<bi多k组的方案数等价于问恰好ai>bi 有(n+k)/2组的方案数恰好->至少 ，先求至少 : 设dp[i][j]为前i个数至少j组满足 a[x]>b[y]的方案数Dp[i][j]=dp[i-1][j](第i个不匹配小的) +dp[...原创 2018-09-08 00:06:53 · 250 阅读 · 0 评论 -
32.hdu6363 因子容斥+模型+数论
32.hdu6363 因子容斥+组合模型+数论题意：有N本一摸一样的书，有一个共有K层的书架，现在要把书都放到书架上。放完后假设第 i层书架有 Bi本书，则该层书架的稳固值为 （2^Bi）-1定义整个书架的美观值为所有层书架的稳固值的GCD问现在随机放这些书，整个书架的美观值的期望值是多少。思路：直接搬得官方题解，很清晰了所以我们只用考虑GCD(x1,x2,x3….)的...原创 2018-09-08 00:12:40 · 179 阅读 · 0 评论 -
31.BZOJ2839 容斥定理+恰有
31.BZOJ2839 容斥定理+恰有 跟3，8，4类似题意：N个元素的集合有2^N个子集，问这些子集中选取若干集合，他们的交集元素个数恰好为K的方案数 N<=1e6思路：先选K个出来，则剩下N-K个元素都没有交集性质：A1:交集元素为1都没有交集=|S|-交集个数至少为1+交集至少为2….|非A1∩非A2∩非A3|=|S|-sum|Ai|+sum|Ai∩A...原创 2018-09-08 00:17:31 · 217 阅读 · 0 评论 -
30.BZOJ4710 容斥定理+相互独立+组合模型
30.BZOJ4710 容斥定理+相互独立+组合模型 跟6类似题意：M种颜色的球，每种球有Mi个，放入N个不同的盒子里，不可以空盒问方案数 M，N，Mi<=1000思路：考虑容斥 Ai为第i个盒子是空盒ans=|非A1∩非A2∩非A3|=|S|-sum|Ai|+sum|Ai∩Aj|-sum|Ai∩Aj∩Ak|sum|Ai|=C(n,1)*【剩下n-1个盒可以为空的方案数】...原创 2018-09-08 00:22:59 · 250 阅读 · 0 评论 -
29.牛客网多校第十场D 组合数+多次前缀和
29.牛客网多校第十场D 组合数+多次前缀和题意：n个数，初始值为0，m个操作 n,m<=1e5 操作3次数小于500操作1：区间l~r+=c操作2：区间1~n每个数变成前缀和操作3：查询l~r加法和 思路：首先我们强行模拟一下前缀和：第0次前缀和 a1, a2 a3 a4第1次前缀和 a1, a1+a2, a1+...原创 2018-09-08 00:27:15 · 664 阅读 · 0 评论 -
CF995F拉格朗日+组合数学+DP
28. CF995F拉格朗日+组合数学+DP，1是根节点若D=3000，有O(nD)的做法：设DP[i][j]为点i的权值是j的方案数，答案就是sum_{i=0}^{D} dp[1][i]Dp[u][j]=对每个邻接点v dp[u][i]=dp[u][i]*( dp[v][j]的前缀和, j<=i)就是说预处理1~3000 用拉格朗日插值搞第d项#includ...转载 2018-09-08 00:30:32 · 311 阅读 · 0 评论 -
46.牛客国庆集训派对day4 E 乒乓球 期望转组合数学+NTT
题意：N个乒乓球权值为wi，每次等概率取出一个（不放回）直到取完，若取出第K个，则获得这颗球左边第一个乒乓球和右边第一个乒乓球的权值的乘积左边没有球了就获得0收益，问期望收益？ N<=1e5 ,模数998244353思路：我们枚举wi*wj产生贡献的情况ans= 其中pij指wi*wj产生贡献的概率我们现在来求pij：1.整个取球过程一共有N！种情况，那...原创 2018-10-09 16:29:25 · 293 阅读 · 0 评论 -
hdu6363组合数学+容斥+扩展欧拉
参考：DLS的代码orz，官方题解 前置技能：1.N个相同的球放K个不同盒子，可以空盒：C（n+k-1,k-1）（插板法可证）2.第二行到第三行可以归纳证明3.扩展欧拉公式，phi(p)=p-1#include<bits/stdc++.h>#define ll long longusing namespace std;const int mod=1e9+...转载 2018-08-08 21:51:30 · 413 阅读 · 0 评论 -
BZOJ4555 NTT或多项式求逆或CDQ+NTT
求这个东西i,j,k<=n,NTT板子题1884ms//如果 r* 2^k +1 是个素数，那么在modr*2^k+1意义下，可以处理 2^k 以内规模的数据，//2281701377=17*2^27+1 是一个挺好的数，平方刚好不会爆 long long//1004535809=479*2^21+1 加起来刚好不会爆 int 也不错//还有就是 998244...原创 2018-08-05 21:36:43 · 258 阅读 · 0 评论 -
uvalive1140 组合数学+二项式反演+预处理cmk
题意：n个位置染m种颜色，选K种颜色，要求相邻位置不同颜色，且K种颜色至少都用一次思路：先选K种颜色，然后如果不管至少都用一次的限制，全体=全体由恰有1种颜色至少用一次+恰有2种颜色至少用一次+..恰有K种颜色至少用一次反演有个黑科技叫二项式反演（容斥）学习博客：http://blog.miskcoo.com/2015/12/inversion-magic-binomial-i...原创 2018-07-29 23:32:00 · 388 阅读 · 0 评论 -
hdu4372 第一类斯特林数
T-T原创 2017-10-13 02:46:51 · 272 阅读 · 0 评论 -
hdu3208 很迷的题，组合数学，精度
T-T转载 2017-10-13 02:52:17 · 251 阅读 · 0 评论 -
刷一波组合数学10.13
orz原创 2017-10-13 03:28:13 · 197 阅读 · 0 评论 -
hdu1124 n!后有多少个0 数学
。。。原创 2017-10-13 03:44:53 · 283 阅读 · 0 评论 -
hdu4045 第二类斯特林，至少k个间隔选数
T-T原创 2017-10-13 03:53:59 · 369 阅读 · 0 评论 -
组合数学小结
组合：n个数取r个的不可重复组合：（n,r） n个数取r个的可重复组合：（n+r-1,r）等价于n个相等的球放进r个不同的箱子的，可以空盒的方案理解：一共n+r-1个坑，选r-1个作为分割线工具：普通母函数Gx=1+x+x^2+x^3........ 排列：n个数取r个不可重复的排列：P（n,r） n个数取r个可重复的排列：n!/(n1!*n...原创 2018-03-27 22:35:05 · 397 阅读 · 0 评论 -
组合数取模小结
非常好的学习博客：https://blog.csdn.net/skywalkert/article/details/52553048下图转至：https://blog.csdn.net/Bfk_zr/article/details/78310541 例题1.hdu5446:lucas+普通CRT求c(n,m)%p 1<=n,m.p<=1e18 保证p为最多15个不...原创 2018-07-29 00:40:19 · 362 阅读 · 0 评论 -
洛谷P4491组合数学+NTT
第一道组合数学+NTT例题1.洛谷P4491 ，给NMS<=1e7题意：N个位置每个位置可以染为M种染色，若位置恰有K种颜色出现S次，则获得愉悦度WK问所有愉悦度之和K的范围：0<=E<=min(M,N/S),设F(i)为位置恰有i种颜色出现S次,由加法原理套路求F(i):从N个位置选i*S个位置 * 从M种颜色选i个颜色*选出来的i*S个位置进行可重集...原创 2018-07-29 09:42:02 · 481 阅读 · 0 评论 -
组合数学刷题姬
例题1.洛谷P4491 ，给NMS<=1e7，NTT题意：N个位置，每个位置可以染为M种颜色，若位置恰有K种颜色出现S次，则获得愉悦度WK问所有愉悦度之和https://blog.csdn.net/animalcoder/article/details/81267633 例题2 hdu5730 CDQ+NTT+DP题意：已知连续i（1<=i<=n...原创 2018-07-29 09:54:29 · 3536 阅读 · 0 评论 -
NTT(FFT)+CDQ优化DP
DP柿子满足卷积形式均可以用CDQ+NTT优化,ai,bi,为两个生成函数的系数 例题1.hdu5322 模数资瓷NTT，ans=dp[n],n<=1e5(下面柿子的(j-1)!应该是(i-1)! )系数ai=dp[i]/i! ,bi=i*i,在CDQ里用NTT#include<cstdio>#include<algorithm>#in...原创 2018-07-29 10:11:32 · 1338 阅读 · 0 评论 -
邻接表的NTT（毒瘤系数开不下二维数组）
Wan fl 20D题意：M个Q群，每个群有si个人，每个群至少选一个，选K个人的方案数思路：每个群挑选的生成函数为,答案就是m个G(i)的生成函数之积后的的系数 生成函数之积NTT，多个相乘，加个分治，此题需要用邻接表。。原来的板子不适用了#include <bits/stdc++.h>using namespace std; const int M...原创 2018-07-29 16:08:48 · 284 阅读 · 0 评论 -
hdu4248 组合数学+DP
0.0原创 2017-10-13 02:10:30 · 307 阅读 · 0 评论