题意 从$1 - n$中任意选择一些数，选$m$次构成$m$个集合 保证： 集合不为空 任意两个集合不相同 集合内各个元素xor起来等于0 Sol 神仙题Orz 我看到两种做法，一种是洛谷题解上的直接dp，另一种是yyb的神仙转化。 其实都差不多吧。。 我简单说一下，设$f[i]$表示选了$i$个集 ...

题意 "题目链接" 给出$n$个数，问任意选几个数，它们$\&$起来等于$0$的方案数 Sol 正解居然是容斥原理Orz，然而本蒟蒻完全想不到。。 考虑每一种方案 答案=任意一种方案 至少有$1$位为$1$的方案 + 至少有两位为$1$的方案 至少有三位为$1$的方案 至少有$i$位为$1$的方案可 ...

在19世纪末，德国数学家康托系统地描绘了一个能够为全部数学提供基础的通用数学框架，他创立的这个学科一直是我们数学发展的根植地，这个学科就叫做集合论。它的概念与方法已经有效地渗透到所有的现代数学。可以认为，数学的所有内容都是在“集合”中讨论、生长的。容斥问题在信息学竞赛的问题求解中也经常出现。 一、知 ...

题意 "题目链接" $n \times n$的网格，用三种颜色染色，问最后有一行/一列全都为同一种颜色的方案数 Sol Orz fjzzq 最后答案是这个 $$3^{n^2} (3^n 3)^n \sum_{i = 1}^n ( 1)^i C_n^i 3(3^{n i} 1)^n + (3^i 3) ...

Description 栋栋有一块长方形的地，他在地上种了一种能量植物，这种植物可以采集太阳光的能量。在这些植物采集能量后， 栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。 栋栋的植物种得非常整齐，一共有n列，每列 有m棵，植物的横竖间距都一样，因此对于每一棵植物，栋栋可以用一个坐标( ...

题意 "题目链接" 给出$n$个数，问最少选几个数，使他们的$gcd = 1$ Sol 好神仙啊qwq。 首先，如果答案存在，那么最多为$7$(因为前$7$个质数乘起来$ = 3e5$) 考虑dp，设$f[i][j]$表示选了$i$个数，他们$gcd = j$的方案数！ 没错是方案数！ 那么我们只要 ...

Description 我们知道，从区间[L,H]（L和H为整数）中选取N个整数，总共有(H L+1)^N种方案。小z很好奇这样选出的数的最大公约数的规律，他决定对每种方案选出的N个整数都求一次最大公约数，以便进一步研究。然而他很快发现工作量太大了，于是向你寻求帮助。你的任务很简单，小z会告诉你一个 ...

题意 询问区间$(l, r)$中有多少个数是只含$6, 8$的数的倍数 Sol 思路很妙啊。 首先在$10^{10}$内只含$6, 8$的数有$\sum_{i = 1}^{10} 2^i = 2046$个。 然后去掉相同的，应该是有$943$个。 之间算不好算，考虑用容斥原理。 但是直接容斥的复杂度 ...

最近ACM时遇到个题，题意如下、 一眼看上去，很简单呀，想都没想就写上了以下代码 一提交 时间超限 ,我就在本地编译器上调试了一下，看了一下题目 (n < 1e9) 便输入 99999999 结果半天没有计算出结果，这肯定超时啦，题目限定时间为 1000 ms 时间不超限就怪了。 既然这样不行，那就 ...

题目描述有 nnn 种颜色的石子，每种 cic_ici​ 个，记一个石子序列首尾相接后极长连续段的长度为 lil_ili​，求所有石子序列的 1∏li!\frac 1{\prod l_i!}∏li​!1​ 的和。n≤105,∑ci≤2∗105n\le10^5,\sum c_i\le2*10^5n≤1...

题意 "题目链接" Sol 首先若y % x不为0则答案为0 否则，问题可以转化为，有多少个数列满足和为y/x，且整个序列的gcd=1 考虑容斥，设$g[i]$表示满足和为$i$的序列的方案数，显然$g[i] = 2^{i 1}$(插板后每空位放不放) 同时还可以枚举一下gcd，设$f[i]$表示满 ...

世界是物质的，物质是运动的，运动是有规律的，规律是可以被认识的 二项式反演 $$ g_n=\sum_{i=0}^n \binom{n}if_i\Rightarrow f_n=\sum_{i=0}^n( 1)^{n i}\binom{n}ig_i $$ 证明如下 $$ \begin{aligned} ...