WEEK201129

HDU6438 Buy and Resell

这个题目挺有意思的,值得记录下来。和以前一道CF一样。它们都是考虑一种“不关心具体方案”时的修改,即利用式子来进行“反悔”。

HDU6439 Congruence equation

记对参数 \(m\),这样的数列 \(\{C_k\}\) 的个数为 \(f(m)\)

  • 长度为 \(k\)
  • 对某些位置限制了必须为某值,而其它位置可以在有限域 \(F_m\) 中任选
  • \(\sum_{1\le i\le k}C_ix_i\equiv1\pmod m\),其中 \(x_i\) 是自由变量,这个方程要有整数解

你要计算 \(\sum_{m=1}^nf(m)\)

\(T\le100,k\le50,n\le10^9\),但最多对\(10\)组数据有 \(n\ge10^6\)


首先入手点当然是那个不定方程了,同余不用怕,多加一个系数为 \(m\) 的变量之后就变成普通不定方程了。

所以有解等价于 \(\gcd(C,m)=1\)\(C\) 是数列中所有数字的简记法。

但是还有一些位置已经定了值,我们不妨把它们先拉出来,把它们的 \(\gcd\) 设为 \(q\)。并且令 \(k\to\text{the number of free var }c_i\)

其实想到到这里应该就知道自己做完了这个不难的题目了,然而我却sb了,看到 \(\gcd=1\) 还想不到反演……

下面记枚举所有数列中不定的位置求和为 \(\sum_{C}\),实际上是 \(k\) 个求和号,那么答案就是

\[ \begin{aligned} \sum_{1\le m\le n}\sum_{C}[(C,q,m)=1] &=\sum_{1\le m\le n}\sum_{C}\sum_{d|(C,q,m)}\mu(d)\\ &=\sum_{d\le n}\mu(d)\sum_{m\le n}\sum_C[d|(C,q,m)]\\ &=\sum_{d\le n}\mu(d)[d|q]\sum_{m\le n}\left(\prod_{1\le h\le k}\sum_{1\le c_h\le m}[d|c_h]\right)\\ &=\sum_{d|q}\mu(d)\sum_{p\le \left\lfloor\large\frac nd\right\rfloor}p^k\\ \end{aligned} \]

这个式子好办,直接枚举因数,然后对于后面那个自然数幂和,暴力\(\mathcal O(k^2)\)预处理伯努利数即可。由于 \(q\le n\le 10^9\)\(\mathcal O(k^2+k\sqrt q)\) 是可以通过的。

当然,此外还有一种情形更棘手些,对于 \(q=0\) ,也就是没有限制,\(d|0\) 是(要视为)恒成立的,也就是 \(d\)\(1\to n\) 枚举。这个时候我们利用和杜教筛类似的交换和号方法可以直接得到

\[ =\sum_{1\le p\le n}p^k\sum_{dp\le n}\mu(d) \]

后面那个是 \(M\left(\left\lfloor\frac nd\right\rfloor\right)\),可以杜教筛,因为显然杜教筛 \(M(n)\) 时其实就会求出所有的 \(M\left(\left\lfloor\frac nd\right\rfloor\right)\)

口胡一下复杂度 \(\mathcal O(k^2+k\sqrt n+n^{2/3})\)

HDU6440 Dream

这个构造还是有点新奇的,幸好 fz 事构造大师hhh,于是我们的方案是这样的

\[ \forall x,y:x+y=1,x\times y=\min(x,y)+1 \]

其中本来是先想出了乘法,这样对幂就有

\[ a\ne0:a^0=1,\;a^1=1\times a=2,\;a^2=3,\;\cdots,\;a^{a-1}=a,\;a^a=a\cdots \]

HDU6442 GuGu Convolution

\(F(x)=\mathrm{EGF}\langle A^0,A^1,A^2,\cdots\rangle(x),G(x)=\mathrm{EGF}\left\langle 0,\left(\sqrt B\right)^1,0,\left(\sqrt B\right)^3,0,\left(\sqrt B\right)^5,\cdots\right\rangle(x)\),求 \(n![x^n](F\times G)(x)\)


比较水,但是很坑。根据 EGF 卷积,答案就是

\[ \sum_{k\text{ is odd}\atop 0\le k\le n}\binom nkA^{n-k}\left(\sqrt B\right)^{k}=\frac12[(A+\sqrt B)^n-(A-\sqrt B)^n] \]

然后显然可以快速幂,有两个坑点

  • 写矩阵快速幂常数太大容易 T,原因是有很多冗余运算,对 \(0\) 运算的那种。可以改成直接做线性变换,省去矩阵操作。
  • 模数任意,但是只要求 \(2\) 的逆元,写个欧拉定理很不值;有个 trick:可以全程 \(\pmod{2p}\) 然后最后换回去的答案是 \(\left\lfloor\dfrac{\rm ans}{2}\right\rfloor\)

评论和共享

WEEK201121

SRM 545 div1 hard SetAndSet

\(n\le50\) 个数 \(V\le2^{20}\),要分成非空的两组,使得对每组把所有数 \(\And\) 起来结果相同。求方案数。


首先分位,对于全 \(0/1\) 的位,随便分直接无视。此外就一定有 \(0\) 了,所以必然是两个集合结果都为 \(0\)。(之前居然想半天没想到这一点,反省……)

然后就可以转化成,两个集合必须都要有 \(0\),发现这个不好做,但是反面很好做,所以考虑容斥。

容斥就要对给定的一些位不合法,不合法意味着 \(0\) 全去了某一边。所以在考虑多个位时,就是关于 \(0\) 有交集的两个位都必须一起划分。

然后用 UFS 合并统计就好了。

Gym 101987G Secret Code

实数区间 \([0,S\le1000]\) 上均匀随机三条线段的开始点,长度分别固定是 \(w_1,w_2,w_3\),问:随机后,线段从左到右,第一条和第二条相交,第二条和第三条相交的概率。


反正是实数,就先考虑写个积分的式子看看。

\[ \int_0^S \mathrm dl_1\int_{l_1}^{\min(l_1+w_1,S)}\mathrm dl_2\min(S-l_2-w_2,w_2) \]

额,也不算很复杂……主要是,反正数值积分那么快,我何必操心它到底啥样呢.jpg

当然,这个东西完全是分段线性的,而且形式摆在那儿了,我们不妨想想怎么直接求。

先考虑 \(l_1-l_2\) 平面,添个纵轴 \(l_3\) ,我们看看哪些点是合法的。

对于前俩轴我们先想个范围,也就是这里积分上下限的限制,显然就是一个斜着的梯形。

而第三条线段只需和第二条相交,也就是说只和 \(l_2\) 有关,又是什么形状呢?还是个梯形 =、= 毕竟限制都是类似的。所以本质其实就是求俩四棱柱(底面是梯形,摆放方向互相垂直)的交的体积。

如图所示,右上角是左边立体图的右视图,分别考虑 \(S_1,S_2\) 两块对应的体积。

\(S_1\) 是个平行四边形,很好办,对应的左边棱柱是个直角三棱锥,也就是说关于 \(l_2\) 是线性的,所以我们可以直接底面积乘高除以二,也就是 \(w_1w_2\cdot\frac{w_1}2\) 这项。

\(S_2\) 是个梯形,看上去比较棘手,但是它对应的棱柱是个等高的东西,就是右视图上某一点对应的体积上的最高点和最低点的高度差是一定的,根据基础几何知识我们知道可以直接用这个高度差乘以底面积。底面积可以补成平行四边形减去一个等腰直角三角形,所以这部分贡献就是 \([(S-w_1)w_2-\frac12w_2^2]w_1\) 这项。

整理一下就得到答案是 \(w_1w_2\left(S-\frac{w_1+w_2}{2}\right)\),简单吧!别忘了考虑全排列嗷!可以枚举俩然后乘二计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 静かな海
#include <bits/stdc++.h>
#define dbg(x, y...) fprintf(stderr, x, y)
#define pline() (dbg("Passing Line #%d in Func [%s]", __LINE__, __FUNCTION__))
using namespace std;

inline int rd() {
int x=0,c,f=1;while(!isdigit(c=getchar()))if(c=='-')f=-1;
for(;isdigit(c);c=getchar())x=x*10+c-'0';return x*f;
}
const int N = 2e6+3;

double w[5];
vector<pair<double, int>> v;

signed main() {
int n = rd();
for (int i=1; i<=n; i++) {
scanf("%lf%lf%lf%lf", w+4, w+1, w+2, w+3);
w[0] = 0;
for (int j=1; j<=3; j++)
for (int k=j+1; k<=3; k++)
w[0] += (2*w[4]-w[j]-w[k])*w[j]*w[k];
v.emplace_back(w[0]/w[4]/w[4]/w[4], i);
}
sort(v.begin(), v.end());
for (auto& x:v) printf("%d ", x.second);
}

易燃易爆杂题

构造一个正整数集合 \(S\subset [4n]:|S|=n\)\(S\) 里每两个元素不互质但不整除。

qwq先想想试试?


= = 假如你和我一样在那里考虑素因子,那就面壁思过去(

\(S=\{2n+2,2n+4,\cdots,4n\}\)

这应该是对于 \(n>1\) 的唯一解。

我太菜了,orzzz易燃

感觉多想一会儿应该能想到的,自己还是太浮躁,而且不擅长应付这类“师出无名”的构造。

什么时候再找 ATC 练练吧。

整点计数 cz_xuyixuan 2019

回来读 19 年集训队论文,没想到发现 xyx 写了以前一个令我印象深刻的题目的超级加强版的命题报告。

关键在于 \(a^2+b^2\) 的高斯整数分解 \((a+b\mathrm i)(a-b\mathrm i)\) ,这样的分解在不考虑乘上一些 \(\omega_4^k\) 的因子的时候是唯一的,于是加法变成了乘法!

咳咳,在 3b1b 找到了这个解法,要看前半部分不如直接看视频吧。

后半部分就是一个积性函数求和,用 \(\min25\) 筛或洲阁筛解决。

评论和共享

拟阵通识

课件

学校好题交流时瞎写的,尽量照顾了线代水平不算高的选手,读起来难度应该不大。

拟阵交也就这一类套路题,还想练练可以做 Rainbow Graph 这题,比赛带上板子就好了。

顺便把课件末尾的几篇资料也读了x

评论和共享

Description

今年多校第一场的题哦

传送门

Analysis

看到积分非常傻眼,而且题目里还声称“答案是有理数”,这自然引起我们的好奇。注意到分子分母其实是齐次的,所以多半是什么东西消掉了才这样的吧x

上下都是 \(4N,2N\) ,不妨只考虑一个 \(N\),然后菜鸡的分析只会大暴力,最暴力的想法就是,呃,先换元试试看。\(x=\frac{1}{\tau}\) 代换后

阅读全文
  • 第 1 页 共 1 页
作者的图片

7mile

八轨宇宙的七里征途


学生


E-Rev