组合数学

这道破题拖了我整整一天。

代数推导

转化为容斥模型

题目所给限制可以表述为,aabb 均为单调不降的序列,长度相等(记为 kk),且 a1=0,ak=n,b1=0,bk=m,i[2,k],ai=ai1bi=bi1a_1=0,a_k=n,b_1=0,b_k=m,\nexists i\in[2,k],a_i=a_{i-1}\land b_i=b_{i-1}

考虑差分序列 ai=aiai1(i[2,k]){a_i}’=a_i-a_{i-1}\quad(i\in[2,k])bi{b_i}’ 同理,它与原序列形成双射。于是不存在 ai=bi=0{a_i}’={b_i}’=0 的差分序列合法。考虑 i=2kai=n\sum_{i=2}^{k}{a_i}’=n,也就是和为 nnk1k-1 元线性方程组的一组非负整数解;bb’ 同理。容易计算“钦定至少有 cc 个位置不合法”的方案数——利用容斥原理即可得到长为 kk 的合法序列对个数为 c=0k2(k1c)(n+(k1)1c(k1)1c)(m+(k1)1c(k1)1c)(1)c\sum_{c=0}^{k-2}\binom{k-1}{c}\binom{n+(k-1)-1-c}{(k-1)-1-c}\binom{m+(k-1)-1-c}{(k-1)-1-c}(-1)^c 答案累加上式结果 ×k\times k(更多…)

More
  • 2022年12月1日

感冒咳嗽,头实在是太晕了,打完前两题和后两题的暴力之后跑去睡了会觉。结果考得还行。

一句话题解

A – 破坏

简单的 O(m2k)\newcommand{\bigO}{\operatorname{O}}\bigO(m2^k) DP。记录每个节点的路径数奇偶性考虑是否翻转即可。

B – 共识

std::bitset 写的暴力大家都会。不过如果你胆子大些,不判断是否为部分分数据范围直接提交(加入随机化的)暴力,将喜提 100 pts\text{100 pts}

命题:现有一个由 2n2n 个元素构成的集合,保证 2n2\mid n。有 n+1n+1 个大小恰为 nn 的子集 S1,,Sn+1S_1,\cdots,S_{n+1}。则至少存在 n/2n/2 对无序对 (i,j),ij,i,j[1,n+1](i,j),i\neq j, i,j\in[1,n+1],使得 SiSjn/2|S_i\cap S_j|\geq n/2

证明(引自宋佳兴学长):记元素 p,p{1,,2n}p,p\in\{1,\cdots,2n\} 在所有子集中出现的次数为 cnt(p)\newcommand{\cnt}{\operatorname{cnt}}\cnt(p)。则显然有“所有子集两两之交的大小” i=1nj=i+1n+1SiSj=p=12n(cnt(p)2)\sum_{i=1}^{n}\sum_{j=i+1}^{n+1}|S_i\cap S_j|=\sum_{p=1}^{2n}\binom{\cnt(p)}{2}

考虑计算该式最小为何。不妨先考虑 (ab)+(nab)\binom{a}{b}+\binom{n-a}{b} 在何时取最小值。

引理(ab)+(nab),bn,a0,an\binom{a}{b}+\binom{n-a}{b}, b\leq n, a\geq 0, a\leq na=n/2a=\lfloor n/2\rfloor 处取最小值。

(更多…)

More
  • 2022年10月26日

LibreOJ #138 类欧几里得算法

题意

T1000T \leq 1000 组数据。给定 n,a,b,c[0,109],k1,k2[0,10],k1+k210n, a, b, c\in [0, 10^9], k_1,k_2\in [0, 10], k_1+k_2\leq 10,求取 x=0nxk1ax+bck2 \sum_{x=0}^{n}x^{k_1}\left\lfloor\frac{ax+b}{c}\right\rfloor^{k_2}

部分分——观察性质

k1=0,k2=1k_1=0,k_2=1 时,是为一般类欧几里得算法的模板。上述链接亦给出了 k1=0,k2=2;k1=1,k2=1k_1=0,k_2=2; k_1=1,k_2=1 时的解法。

k2=0k_2=0 时,该式退化为 x=0nxk1\sum_{x=0}^{n}x^{k_1},即 k1k_1 次的等幂求和。有一个模糊的结论:

nn 为正整数。则kk 次的等幂求和,x=0nxk\sum_{x=0}^{n}x^k,是一个关于 nnk+1k+1 次多项式。

该结论来源于 zyw 学姐多项式专题所选题目 BZOJ 3453 – tyvj 1858 XLkxc。之所以说模糊,是因为该多项式的系数是已知的。不过我们仍然可以暴力计算 k+2k+2 个点以插值。

再观察 OI-Wiki 上对于 k1+k22k_1+k_2\leq 2 时的解法。在求取 h(n,a,b,c)=x=0nax+bc2h(n,a,b,c)=\sum_{x=0}^n\left\lfloor\frac{ax+b}{c}\right\rfloor^2时采取了如下转化:

x2=2×x(x+1)2x=2(y=1xy)xx=0nax+bc2=x=0n2(y=1ax+bcy)ax+bc\begin{aligned} x^2&=2\times \frac{x(x+1)}{2}-x\\ &=2\left(\sum_{y=1}^{x}y\right)-x\end{aligned} \quad\begin{aligned} \Longrightarrow\sum_{x=0}^n\left\lfloor\frac{ax+b}{c}\right\rfloor^2=\sum_{x=0}^n2\left(\sum_{y=1}^{\left\lfloor\frac{ax+b}{c}\right\rfloor}y\right)-\left\lfloor\frac{ax+b}{c}\right\rfloor\\ \end{aligned}

这样一来,由于 yy 是一个线性算子,在 ax+bycax+b\geq yc 时都有 yy 向总和贡献,于是我们可以应用类似于 k1=0,k2=1k_1=0,k_2=1 时的方法转化贡献。这个过程对 k2k_2 作了降次。

那么,对于更高次项,有无办法采取同样的办法转化呢?是否可以设计一些转化,使得要求取的函数 f(,k1,k2)f(\cdots,k_1,k_2) 能够由 f(,k1?,k2?)f(\cdots,k_1-?,k_2-?) 推出呢? (更多…)

More
  • 2022年10月13日

Educational Codeforces Round 133 F – Bags with Balls

题目中存在高次项的和。则我们分别计算有 p=1,2,,np=1,2,\cdots,n 个袋子选择奇数号球时的方案。对于选择了奇数号球的袋子,每个有 m2\lceil \frac{m}{2} \rceil 种选择;偶数的则有 m2\lfloor \frac{m}{2} \rfloor 种。因此答案为: p=0npk(np)m2pm2np \sum_{p=0}^{n}p^k\dbinom{n}{p}\Big\lceil\frac{m}{2}\Big\rceil^p\Big\lfloor \frac{m}{2} \Big\rfloor^{n-p}

由于 n109n\leq 10^9,这式子看起来非常棘手。但我们注意到,有 k2000k\leq 2000,这提示我们或许应该转变对答案的贡献方式:从高次幂入手,找到 O(polyk)\mathrm{O}(\operatorname{poly} k) 而非 O(n)\mathrm{O}(n) 的算法。 (更多…)

More
  • 2022年8月8日

二项式反演

有数论函数 f,gf,g,则 nN,\forall n \in \mathbb{N}, f(n)=x=0n(nx)g(x)    g(n)=x=0n(1)nx(nx)f(x)(1)f(n)=x=0n(1)x(nx)g(x)    g(n)=x=0n(1)x(nx)f(x)(2)f(n)=x=n+(xn)g(x)    g(n)=x=n+(1)xn(xn)f(x)(3)\begin{aligned} f(n)=\sum\limits_{x=0}^{n}\dbinom{n}{x}g(x) &\iff g(n)=\sum\limits_{x=0}^{n}(-1)^{n-x}\dbinom{n}{x}f(x) && (1)\\ f(n)=\sum_{x=0}^{n}(-1)^x\dbinom{n}{x}g(x) &\iff g(n)=\sum\limits_{x=0}^{n}(-1)^x\dbinom{n}{x}f(x) && (2)\\ f(n)=\sum_{x=n}^{+\infty}\dbinom{x}{n}g(x) &\iff g(n)=\sum_{x=n}^{+\infty}(-1)^{x-n}\dbinom{x}{n}f(x) && (3) \end{aligned}

(6月22日追记:式 (1),(3)(1),(3) 在OI中是最常用的。尤其是 (3)(3),阐述了在计数类问题中钦定 xx 个元素满足某种属性(f(x)f(x)),其他元素任意,与恰好xx 个元素满足某种属性(g(x)g(x))之间的对应关系。)

证明

(更多…)

More
  • 2022年6月21日

一场相当有收获的比赛。比赛链接

A – 石老板举世无双

解法一

尝试观察规律。我们发现,在完成ss次操作以后,左端点的可能取值为xa+(2sx)b2s,x[1,2s]\dfrac{xa+(2^s-x)b}{2^s}, x \in [1, 2^s],右端点的可能取值为xa+(2sx)b2s,x[0,2s)\dfrac{xa+(2^s-x)b}{2^s}, x \in [0, 2^s)。假如现在我们达到最终状态,其l=(x+1)a+(2sx1)b2s,r=xa+(2sx)b2sl=\dfrac{(x+1)a+(2^s-x-1)b}{2^s}, r=\dfrac{xa+(2^s-x)b}{2^s}。那么,在xx的二进制表示中,如果从高到底pos\mathrm{pos}位为11,则在第pos\mathrm{pos}轮中,有check (mid) == 0,向右区间递归;否则向左区间递归。这是很容易解释的:若向右递归,则右端点不变。而在下一层,右端点表示中a,ba, b的所有系数乘22,所以体现为二进制位末尾添一个00。反之,就变成(x+(x+1))/2(x+(x+1))/2,在下一层中体现为2x+12x+1。如果其有popc(x)\operatorname{popc}(x)位为11,则到达该状态的概率为p0popc(x)p1spopc(x)p_0^{\operatorname{popc}(x)}p_1^{s-\operatorname{popc}(x)}

s=3s=3时的状态l=3a+5b8,r=2a+6b8l=\dfrac{3a+5b}{8}, r=\dfrac{2a+6b}{8}为例。22的三位二进制表示为0b010\text{0b010},则推断出在前三轮分别向右、左、右区间递归,到达其的概率为p0p12p_0p_1^2(更多…)

More
  • 2022年5月17日

被这玩意卡了一上午——前天CSP-S模拟的T4需要用到这类问题的转移。为什么题解TMD是错的?

g(i,j,k)g(i,j,k)表示“每个位置有ii类元素可选,且序列中必须包含指定的jj类元素的,长度为kk的序列的个数”。形式化地讲,我们需要统计满足以下条件的序列的个数:p[1,k],apS (S=i);bTS (T=j),p[1,k],ap=b\forall p \in [1,k], a_p \in S\space(|S|=i); \forall b \in T \subseteq S\space(|T|=j), \exists p \in [1,k], a_p=b

通过容斥原理,我们可以计算出至少有0,1,2,,j0,1,2,\dots,jTT中的元素没有被包含在序列中的序列的个数,然后乘上容斥系数累加既是答案。也即: g(i,j,k)=x=0j(1)x(jx)(ix)kg(i,j,k)=\sum\limits_{x=0}^{j}(-1)^x\dbinom{j}{x}(i-x)^{k}。通俗地讲,我们在 jj 个元素中选择 xx 个,并强制使得它们不出现在序列中,其余元素任选。除去组合数的预处理时间,复杂度为O(j)\mathrm{O}(j)。参阅AtCoder ABC 194 F – Digits Paradise in Hexadecimal可以使用上述计算而非DP求解(虽然DP更加简洁直观)

(更多…)

More
  • 2022年3月4日