CVBB ACM Team

AB

题意:设$f(n)$为满足$x^2 + y^2 + z^2 + xy + yz + zx = n$的$(x,y,z)$三元组个数，求$f(1),f(2), \cdots , f(N)$。$(1 \leq N \leq 10^4)$

题意:定义$f(n)=n \mod \mathrm{popcount}(n)$，给出一个$N$位的二进制串，若只将从高到低第$i$位反转，对应的十进制数经过多少次$f$变换变为$0$。$(1 \leq N \leq 2 \times 10^5)$

题解:可以发现将大串进行一次$f$变换后数据范围很小就可以直接暴力，而第一次变换模数只有两种，设原本$1$的个数为$x$，则只有$x+1$和$x-1$两种，预处理扫一遍即可。

题意:有$N$个骆驼，对他们进行排列。第$i$个骆驼如果在前$k_i$个，它的权值为$l_i$，否则权值为$r_i$，求最大的权值和。$(1 \leq N \leq 2 \times 10^{5})$
题解:考虑将$l_i>r_i$与$l_i<r_i$的骆驼分为两组，分别讨论。显然两组交集为空，第一组骆驼尽量向左放，第二组骆驼尽量向右放，互不冲突，因此可以独立进行讨论。对于每一组，按照$k_i$（或$n-k_i$）从小到大进行排序，维护一个小根堆存放目前可以取到更大值的骆驼，如果堆中数量小于$k_i$（或$n-k_i$）则直接放入堆中，否则看是否比堆顶元素大，大的话将堆顶元素替换为更大的即可。

题意:设十元组$(s_1,s_2,n_1,n_2,u_1,u_2,k_1,k_2,e_1,e_2)$满足下列条件，$0 \leq s_1 < s_2,0 \leq n_1 < n_2,0 \leq u_1 < u_2,0 \leq k_1 < k_2,0 \leq e_1 < e_2,$$s_1 + s_2 + n_1 + n_2 + u_1 + u_2 + k_1 + k_2 + e_1 + e_2 \leq N$，求所有满足条件的十元组的$(s_2 − s_1)(n_2 − n_1)(u_2 − u_1)(k_2 - k_1)(e_2 - e_1)$的和，对$10^{9} +7$取模。$(1 \leq N \leq 10^{9})$

题解:设$\Delta{s}=s_2-s_1$，其它变量同理，则有$\Delta{s},\Delta{n},\Delta{u},\Delta{k},\Delta{e} > 0, 2s_1 + \Delta{s} + 2n_1 + \Delta{n} + 2u_1 + \Delta{u} + 2k_1 + \Delta{k} + 2e_1 + \Delta{e} \leq N$，求所有满足条件的十元组$(s_1,\Delta{s},n_1,\Delta{n},u_1,\Delta{u},k_1,\Delta{k},e_1,\Delta{e})$的$\Delta{s}\Delta{n}\Delta{u}\Delta{k}\Delta{e}$的和。构造生成函数：$2s_1$对应$1+x^2+x^4+ \cdots = \dfrac{1}{1-x^2}$，有$5$个所以乘以五次方，得到$\dfrac{1}{{(1-x^2)}^5}$；$\Delta{s}$因为最后要求的是不是方案数而是乘积和，因此对应$x+2x^2+3x^3+ \cdots = \dfrac{x}{{(1-x)}^2}$，有$5$个所以乘以五次方，得到$\dfrac{x^5}{{(1-x)}^{10}}$；最后因为求的是$\leq N$，还要乘以一个$1+x+x^2+ \cdots = \dfrac{1}{1-x}$求前缀和。最后这三个乘起来得到$f(x)=\dfrac{(1+x)^{11}x^5}{(1-x^2)^{16}}$，因此我们只需要知道$\dfrac{(1+x)^{11}}{(1-x^2)^{16}}$展开后$x^{N-5}$的系数即可。观察发现分子分母单独拿出来都很好展开，而分子展开后只有有限的$12$项，因此我们只用枚举分子的每一项，计算出分母对应项系数的和，将两个系数乘起来最后加起来即可。