更好的阅读体验update2024-11-1211:25修改了一些格式错误且增加了二项式反演的例题2024-11-1214:33改进了二项式反演的证明基础知识一、加法原理完成某个工作有\(n\)类办法，第\(i\)类办法有\(a_i\)种，则完成此工作的方案数有\(\sum\limits_{i=1}^na_i\)种。二

计数问题的思考方法——以《[ARC102E]Stop.Otherwise...》为例DP如果要使用DP，则重点在其状态的设计，即我已经考虑了什么，当前正在考虑什么，通过一个不断将考虑范围扩大的方法，得到答案。在转移的过程中，往往通过当前决策点的不同状态，从不同的状态转移过来（或转移到不同的状态），以得

最近模拟赛抽象题太多了，让他们聚一聚T1多校A层冲刺NOIP2024模拟赛18T3DBA暴力比较显然，直接数位dp就好，记搜的复杂度是\(O(n^4)\)的，用递推加前缀和优化可以优化为\(O(n^3)\)，但我还是不理解\(O(n^3)\)凭啥能\(拿97pts\)，虽然和正解没啥关系，但还是放一下记搜的代码：点击查看代码

T1选彩笔（rgb）观察到值域较小，考虑静态值域三维偏序，人话：三维前缀和。三维前缀和的式子：get(i,j,k,x,y,z)=s[i][j][k]-s[i][j][z-1]-(s[i][y-1][k]-s[i][y-1][z-1])-(s[x-1][j][k]-s[x-1][y-1][k]-s[x-1][j][z-1]+s[x-1][y-1][k-1]);，直接几何意义推的，但是高维前缀和有通式。然后二分

2024.6.27T1题面给定一个正整数序列\(a_{1\simn}\)，以及一个正整数\(P\)，求有多少的三元组\((i,j,k)\)满足:\(1\lei<j<k\len\)\(P=a_i\times2^{\lfloor\log_2a_j\rfloor+\lfloor\log_2a_k\rfloor+2}+a_j\times2^{\lfloor\log_2a_k\rfloor+1}+a_k\)\(多

CF660E长度为\(0\)的子序列的答案就是\(m^n\)。长度为\(k\)的子序列的答案为：\[m^k\sum_{i=k}^n{i-1\choosek-1}(m-1)^{i-k}m^{n-i}\]解释就是：\(m^k\)为这个子序列的样子的方案数，后面枚举的是这个子序列最后一个元素的位置，组合数是选前面\(k-1\)个数的位置。因为

参考:link1，link2定义竞赛图是指一类对于任意两个点之间有且只有一条有向边的有向图，下面记\(G=(V,E),n=|V|,m=|E|\)，我们称一个\(|V|=n\)的竞赛图为\(n\)阶竞赛图。性质竞赛图缩点后是链状结构考虑按照tarjan算法缩点后，对于\(col_u<col_v\)，必有边\(v\tou\)，这是因为

前言校测被数学干碎了，赶紧来补一点容斥和反演的东西，能补多少算多少吧。特别说明：这一篇学习笔记是组合数学的第二篇。反演这是一个听着很高大上，实际不简单（因为wtcl）的东西。反演的实质对于形如下面的式子，我们称左右两式互为反演式：\[f_i=\sum^{i}_{j=1}A_{i,j}g_j\Leftrightar

theinstallationofthedevenvironmentofesp32someconditionusevscodesimplestepschoosethepulginsofidfthendownloadthepulginsandenterthemainpagechoosethefistchoicethenyouchoosethebersionofidfandthepathofitwaitpat

换根dp模板题。\(f_i\)是在以\(i\)为根的子树中，以\(i\)为链的一个端点且\(i\)在点集中的合法点集个数。\(ans_i\)表示包含\(i\)的合法点集个数。当\(x\)为树根时：\[ans_x={f_x\choose2}-\sum_{s\inson}{2f_s+1\choose2}+f_x\]简单解释一下，\({f_x\ch

我打析合树？真的假的？要上吗？A把异或值二进制分解，根据期望线性性，\(E((\sum\limits_{i=0}^ka_ix^i)^2)=E(\sum\limits_{i=0}^k\sum\limits_{j=0}^ka_ia_jx^{i+j})=\sum\limits_{i=0}^k\sum\limits_{j=0}^kE(a_ia_j)x^{i+j}\)，而\(E(a_ia_j)\)就是选出的子集的异或值的\(i,j\)位

观察以下式子：\[\begin{aligned}&1^3=1=1\\&2^3=8=3+5\\&3^3=27=7+9+11\end{aligned}\]猜到：\[n^3=\frac12n[(n^2-n+1)+(n^2-n+1+2n-2)]\\\]可证明正确。那么\[\begin{aligned}&\sum_{i=1}^ni^3\\=&\f

1.课后实验：出三十道一百以内的四则运算importjava.util.Random;publicclasshomework{publicstaticvoidmain(String[]args){intnum1,num2,temp,choose;num1=0;num2=0;temp=0;choose=0; for(inti=1;i<=30;i++) { choose=add();//将随机得到一个一百以内的

原题链接：P1313[NOIP2011提高组]计算系数。难度：Easy。考察二项式定理的基本应用。正解发现存在式子\((ax+by)^k\)，容易想到二项式定理。二项式定理：\[(x+y)^n=\sum\limits_{i=0}^{n}{n\choosei}x^iy^{n-i}\]令\(p=ax,q=by\)，那么原式变为\((p+q)^k\)。那么此时

简要题意一个有\(N\)个元素的集合有\(2N\)个不同子集（包含空集），现在要在这\(2N\)个集合中取出若干集合（至少一个），使得它们的交集的元素个数为\(K\)，求取法的方案数，答案模\(10^9+7\)。数据范围：\(1\leK\leN\le10^6\)。题解我们设\(f(i)\)表示选出子集大小恰好为\(i\)的

前言计数加训！！！！以下问题都是数数。一些纯组合问题插板法例1求$\sum_{i=1}^kx_i=n$的解的组数，其中$x_i\in\mathbb{N^+}$且$x_i\gea_i$。考虑令$x_i'=x_i-a_i+1\ge1$，于是有$\sum_{i=1}^kx_i'=n-k+\suma_i$，于是答案为$$n-k+\suma_i-1\choosek-1$$例2从$1\do

题目传送门题目大意：设函数\(F(x):=(x+1)\bmod3−1\)，\(T\)次询问，计算：\[\sum\limits_{i=0}^{n}\sum\limits_{j}F\left({i\choosej}\right)\]思路：看到奇奇怪怪的组合数求和首先考虑\(\text{Lucas}\)，将原数在\(3\)进制下拆位，得：\[{i\choosej}=\prod\limits_{k

name=input('输入姓名')ifname=='kk':print('hellokk')ifname=='k':print('hik')name=input('输入姓名')ifname=='kk':print('hellokk')else:print('fxxk')gif

！！！有需要的小伙伴可以通过文章末尾名片咨询我哦！！！ 

前言计数的基本原理考虑一个集合：\(S\)，求\(|S|\)。加法原理：\(S=S_1\cupS_2,|S|=|S_1|+|S_2|\)。乘法原理：\(|{(a,b)|a\inS_1,b\inS_2}|=|s_1||s_2|\)更浅显的说当两件事情无关时为加法，当前一件的结果影响后面时用乘法。组合数基本公式及衍生公式排列与组合排列

组合恒等式:1.\(n\choosem\)=\(n-1\choosem\)+\(n-1\choosem-1\)2.下降幂\(n^{m}\)就是\(A^{m}_{n}\)3.\(\sum^{m}_{i=0}{i\choosen}={m+1\choosen+1}\)4.范德蒙德卷积\(\sum^{k}_{i=0}{n\choosei}{m\choosek-i}={n+m\choosek}\)5.\(\sum_{i

数学数论唯一分解定理定理对于任意正整数\(a\)，均有：\[a=p_1^{k_1}p_2^{k_2}\cdotsp_n^{k_n}\]其中\(p_1,p_2\cdotsp_n\)均为质数。约数和公式对于任意正整数\(a=p_1^{k_1}p_2^{k_2}\cdotsp_n^{k_n}\)，其约数和\(k\)为\[k=({p_1}^0+{p_1}^1+\cdots{p_1}^{k_1})({p

二项式定理$\quad\quad\quad(x+y)^n=\sum_{k=0}^{n}{n\choosek}x^{n-k}y^k$证明\(\quad(x+y)^n=(x+y)*(x+y)*(x+y)*...\)我们考虑多项式乘法\((a+b)*(a+b)=a*a+a*b+b*a+b*b\)于是我们枚举每个因子相乘，可以发现\((x+y)^n\)每个括号里的\(x\)和\(y\)最多只能选

卢卡斯定理常用于求组合数，且质数模数\(p\)较小时的情况（常常与费马小定理结合使用，要是\(p\)不是质数直接上扩欧就可以了）。那为什么要用卢卡斯定理？因为虽然\(p\)是质数，但是如果\(x>p\)，那么他俩不一定互质，所以\(x\)在模\(p\)意义下不一定存在逆元，那我们的组合数公式无法

实在有必要单独拿出来说说，我一直认为我的计数能力相较其他能力是较突出的，但是最近做到的题目让我不得不怀疑我到底会不会做计数题。做计数时还是只能靠灵光一现吗？那这样的题目叫我怎么灵光一现？所以有必要好好总结计数题的常见技巧。当然因为样本量有限，所以可能会漏掉某些重要的技